Théorie des graphes
Le terme de graphe désigne en mathématiques une opération d'application. Il possède deux acceptions :
- le graphe d'une Fonction (à distinguer de sa représentation graphique)
- un objet représentant une relation binaire, orientées ou non, entre des éléments d'un ensemble.
La théorie des graphes concerne cette seconde acception.
| Sommaire |
Définition formelle
On nomme graphe un couple (S,A), S étant un ensemble et A une partie de S×S (produit cartésien d'ensembles).
Les éléments de S sont appelés les sommets, le nombre de sommets se nomme l'ordre du graphe.
On distingue deux types de graphes:
- les graphes non orientés, où la relation binaire entre sommets est symétrique ; les éléments de A sont des paires (sans ordre) de sommets et se nomment arêtes.
- les graphes orientés, où la relation binaire n'est pas symétrique ; les éléments de A sont des couples (ordonnés) de sommets et se nomment arcs (là où une relation est symétrique, on la matérialise alors par deux arcs de sens opposé)
Quand on parle de graphes non orientés, il est admis de ne pas en préciser le type.
Graphiquement, une relation entre deux sommets d'un graphe orienté peut se représenter à l'aide d'une flèche entre ceux-ci. Dans le cas d'un graphe non orienté, c'est un trait qui symbolise cette relation.
Tout graphe comporte une matrice associée . Celle ci est d'ordre n ( n représentant le nombre de sommets ) et de dimension n x n .
le nombre à l'intersection de la i-ème ligne et de la j-ème colonne vaut k, nombre d'arêtes reliant i et j.
Les sommets sont dits adjacents lorsqu'ils sont reliés par une arête .
Exemples
- Un réseau routier peut se représenter comme un graphe (non-orienté, sauf si l'on tient compte d'éventuelles voies à sens unique) dont les sommets sont les villes et les arêtes les routes qui mènent directement d'une ville à une autre sans passer par une ville intermédiaire.
- Un réseau de neurones formels peut se représenter par un graphe orienté valué (chaque arc porte une valeur), et dont chaque sommet est valué aussi de son seuil d'activation.
- Le réseau internet est un graphe dont les sommets sont les serveurs et les utilisateurs et les arêtes les différentes interconnexions.
Champ d'utilisation
La théorie des graphes étudie les propriétés de ces objets. Parmi les problèmes classiques figurent :
- le problème des sept ponts de Königsberg ou la recherche de cycles eulériens.
- la connexité: existe-t-il un chemin reliant deux sommets ?
- arbres couvrants de poids minimaux
- le plus court (respectivement long) chemin entre deux sommets d'un graphe valué
- la coloration de graphe avec un nombre fixé de couleurs
- les sous-graphes denses maximaux (parfois appelés cliques)
- les problèmes de flots maximaux ou minimaux
- allocations de ressources
- le problème du voyageur de commerce
- le problème du postier chinois
- décomposition d'un graphe en niveaux
- la gestion de projet avec le réseau PERT
- graphes hamiltoniens et hypohamiltoniens
Cette théorie est fortement liée à l'algorithmique et à la complexité.
Définitions
Arbre couvrant minimal
- Un arbre couvrant minimal est un arbre couvrant d'un graphe pondéré dont la somme des poids des arêtes est minimal.
Boucle
- Arête dont les extrémités sont confondues. Notion utile en théorie des automates.
Carré d'un graphe
- Le carré d'un graphe est le graphe qui a les mêmes sommets et dont deux sommets sont reliés s’ils sont reliés dans le graphe d'origine ou s’ils ont un voisin en commun dans le graphe d'origine.
Chemins et chaînes
- Dans un graphe orienté, un chemin entre deux sommets a et b est une suite finie de n sommets (si) tels que a = s1, b = sn et pour tout i dans [1, n-1] il existe une arête entre si et si+1. Un chemin est dit élémentaire si un sommet y est présent au plus une fois.
- Dans le cas d'un graphe non-orienté, on parle de chaîne.
Chaîne eulérienne
- Une chaîne eulérienne est une chaîne composée de toutes les arêtes d'un graphe prises chacune une et une seule fois.
- Un graphe connexe possède une chaîne eulérienne si et seulement si tous ses sommets sont de degré pair à l'exception d'au plus 2 d'entre eux.
Chaîne hamiltonienne
- Une chaîne hamiltonienne est une chaîne composée de tous les sommets d'un graphe pris chacun une et une seule fois.
Cycles et circuits
- Si un sommet est à la fois premier et dernier d'un chemin ou d'une chaîne, alors ce chemin ou cette chaîne est appelé un cycle. Dans le cas d'un graphe orienté, on utilise le terme de circuit.
Cycle eulérien
- Un cycle eulérien est une chaîne eulérienne dont les extrémités sont confondues.
- Un graphe connexe possède un cycle eulérien si et seulement si tous ses sommets sont de degré pair.
Cycle hamiltonien
- Un cycle hamiltonien est une chaîne hamiltonienne dont les extrémités sont confondues.
Degré
- Dans un graphe non orienté, le degré d'un sommet est le nombre d'arêtes issues de ce sommet. La somme des degrés de chaque sommet est égale au double du nombre total d'arêtes..
- Dans un graphe orienté, on distingue pour un sommet v le degré entrant et le degré sortant. Le premier correspond au nombre d'arcs dont l'extrémité finale est v. Le second est le nombre d'arcs dont l'extrémité initiale est v. Le degré d'un sommet v dans un graphe orienté est la somme du degré entrant et sortant de v.
Ensemble dominant
- Un ensemble dominant est un sous-ensemble de sommets du graphe tels que chaque sommet du graphe est soit dans l'ensemble dominant, soit est voisin d'un sommet de l'ensemble dominant
Ensemble stable
- Un ensemble stable est un sous-ensemble de sommets du graphe qui ne sont pas reliés entre eux par une arête. C'est-à-dire un sous-ensemble de sommets qui ne comporte pas deux sommets voisins.
Graphe inverse
- Le graphe inverse d'un graphe est un graphe qui a les mêmes sommets, reliés si et seulement s’ils ne sont pas reliés dans le graphe d'origine.
Partition
- Une partition des sommets d'un graphe est une famille disjointe d'ensembles de sommets telle que leur union est l'ensemble de tous les sommets.
Sous graphe
- Soit G=(S,A) un graphe, un sous-graphe induit ou sous-graphe de G, est un graphe G'=(S',A'), où:
-
- Si
, G' est sous-graphe couvrant.
- Si
, G' est un sous-graphe partiel.
Arbre couvrant
- Un arbre couvrant d'un graphe est un arbre qui passe par tous les sommets du graphe, et dont les branches sont un sous-ensemble des arêtes du graphe. Tout graphe connexe admet un arbre couvrant. Chaque sommet du graphe est la racine d'un arbre couvrant du graphe.
Sous-graphe complet ou clique
- On nomme clique un sous-graphe complet. Une p-clique est une clique de p sommets. :Cette notion est utile pour constituer des groupes en classification automatique.
Sous-graphe stable ou ensemble stable
- Un stable est un sous-graphe sans arêtes...
Valuation d'un graphe
- Une valuation d'un graphe est une fonction qui, à chaque arête, associe un poids (nombre réel).
- Exemples : Une valuation possible d'un réseau routier est la longueur de la route. Une autre, le montant du péage à acquitter entre deux points, ou celle de toute autre ressource pour aller d'une ville à l'autre (consommation de carburant, coût, temps, etc.).
Classes de graphes
Arbre
- On nomme arbre un graphe connexe acyclique (sa forme évoque en effet la ramification des branches d'un arbre). On distingue deux types de sommets dans un arbre
- les feuilles dont le degré est 1 ;
- les nœuds internes dont le degré est supérieur à 1.
Arborescence
- Type arbre, dans le cas où les branches sont orientées et que l'arbre possède une racine.
Forêt
- Une forêt est un graphe acyclique. Chacune de ses composantes connexes est donc un arbre.
Graphe biparti
- Un graphe est biparti s’il y a une partition des sommets du graphe en deux sous ensembles A et B telle que toutes les arêtes du graphe ont un sommet dans A et un sommet dans B.
Graphe complet
- Un graphe complet est un graphe dont tous les sommets sont reliés deux à deux. Le graphe complet à n sommets est noté: Kn.
- voir l'article Graphe complet.
Graphe connexe
- Un graphe non orienté est connexe, si et seulement si pour toute paire de sommets [a,b] il existe une chaîne entre les sommets a et b.
- Si on parle de connexité pour un graphe orienté, c'est que l'on considère non pas ce graphe, mais le graphe non-orienté correspondant.
Graphe k-connexe
- Un graphe non orienté est k-connexe s'il reste connexe après suppression d'un ensemble quelconque de k-1 arêtes et s'il existe un ensemble de k arêtes qui déconnecte le graphe. Autrement dit, un graphe est k-connexe si et seulement s’il existe au moins k chaînes indépendantes (arcs-disjointes) entre chaque couple de sommets. Cette notion est utilisée en électronique, en calcul de la fiabilité, et dans l'étude de jeux de stratégie comme le cut and connect.
Graphe fortement connexe
- Un graphe orienté est dit fortement connexe, si pour tout couple de sommets (u,v) du graphe il existe un chemin de u à v et de v à u. Les travaux de Pitts et McCullough suggèrent que le cerveau des mammifères est fortement connexe.
Graphe hamiltonien
- Graphe qui contient un cycle hamiltonien. Le graphe est nommé hypohamiltonien s'il suffit d'en retirer un sommet quelconque pour qu'il devienne hamiltonien. Utile dans le problème du voyageur de commerce.
Graphe d'intervalles
- Si I est un ensemble d'intervalles sur les réels et qu'on peut associer à chaque sommet un intervalle et que pour chaque sommets u et v il y a une arête entre u et v si et seulement si l'intersection entre leurs intervalles associés n'est pas nulle, alors le graphe défini par ces sommets et ces arêtes est un graphe d'intervalles.
Graphe de permutation
- Soit P une permutation de la séquence 1,...,n. Le graphe d'inversion associé à P est le graphe dont les sommets sont les entiers 1,...,n et dont pour tout sommets u et v il y a une arête entre u et v si et seulement si u et v sont inversés dans P.
- Un graphe est un graphe de permutation s’il existe une permutation dont le graphe est son graphe d'inversion.
Graphe planaire
- Un graphe est planaire s'il existe au moins une façon de le dessiner dans le plan sans que deux arêtes se croisent. Cette propriété est importante pour les circuits imprimés monocouche.
Graphe k-régulier
- Un graphe régulier est un graphe où chaque sommet est de degré k.
Graphe simple
- Graphe sans boucle, et très simple de personnalité.
Graphe split
- Un graphe est split s’il existe une partition des sommets du graphe en deux sous-ensembles S et C telle que S est un ensemble stable et C est une clique.
Algorithmes importants de la théorie des graphes
Algorithmes de plus court chemin
- Algorithme de Dijkstra
- Algorithme de Dantzig
- Algorithme de Ford-Bellman
Algorithme d'arbres couvrant minimaux
Algorithme pour les flots maximums
- Algorithme de Ford-Fulkerson
- Algorithme de Roy
Algorithmes de parcours de graphe
- Algorithme de parcours en largeur (ou BFS: Breadth first search)
- Algorithme de parcours en profondeur (ou DFS: Depth First Search)
Algorithmes de coloration
(voir coloration de graphe)
Algorithmes divers
- Algorithme du plus proche voisin
- Algorithmes de connexité
Liens externes
- Théorie des Graphes Cours de théorie des graphes