Cours des Graphes - Recherche Operationnnelle
Les graphes
Pourquoi les graphes ?
Le problème des trois bocaux
Le problème des ponts de Königsberg
Théorème d'Euler : Un multigraphe simple (sans boucle) G admet une chaîne eulérienne si et seulement si il est connexe (“d'un seul tenant”) et si le nombre de sommets de degré impair est 0 ou 2.
Définitions élémentaires
•Un graphe orienté est un couple G = (X,U ), où X est un ensemble dont les éléments sont appelés sommets et U une partie de X × X dont les éléments sont appelés arcs.
•Un graphe non orienté est un couple G=(X,E), où X est un ensemble dont les éléments sont appelés sommets et E un sous-ensemble de parties de X contenant chacune au plus 2 éléments et dont les éléments sont appelés arêtes.
•Un chemin est une suite de sommets [x0 , x1 , .... , xp ] telle que les arcs (x0 , x1 ) , ( x1 , x2 ) , ..... , ( xp-1 , xp ) appartiennent au graphe. La valeur d'un chemin est alors la somme des valuations des arcs de ce chemin. La longueur d'un chemin est son nombre d'arcs.
•Une chaîne est une suite d'arcs u1, u2 , .... , up telle qu'une extrémité de l'arc ui (2 ≤ i ≤ p-1 ) est commune avec l'arc ui+1, alors que l'autre extrémité est commune avec l'arc ui-1. La longueur d'une chaîne est son nombre d'arcs.
• Un sous-ensemble S de X est stable s'il n'y a pas d'arc reliant deux sommets de S. Le nombre de stabilité α(G) est le cardinal maximal d’un ensemble stable.
• Un graphe G est c-chromatique s'il est possible d'en colorier les sommets avec c
couleurs sans que deux sommets adjacents soient de même couleur. Le nombre chromatique γ(G) est le plus petit c tel que G soit c-chromatique.
Codage d’un graphe
• Matrice associée
Graphes associés
• Graphe partiel
Connexité
• Connexité simple : composantes connexe
• Connexité forte : composantes fortement connexe
Graphes particuliers
• Une forêt est un graphe sans cycle
• Un arbre est un graphe connexe sans cycle
Il est sans cycle et comporte n-1 arêtes.
Il est connexe et si on enlève une arête il n'est plus connexe.
Il est sans cycle et on crée un cycle si on ajoute une arête.
Il existe une chaîne élémentaire et une seule entre toute paire de sommets.
• On appelle arborescence un arbre orienté tel que chaque sommet (sauf un) a exactement un prédécesseur. Le sommet sans prédécesseur est la racine de l'arborescence.
