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
• File des successeurs

 Graphes associés


• Graphe partiel
• Sous-graphe
• Sous-graphe partiel
 • Fermeture transitive

 Connexité


• Connexité simple : composantes connexe
• Connexité forte : composantes fortement connexe 

• Graphe réduit :

Graphes particuliers

• Une forêt est un graphe sans cycle

• Un arbre est un graphe connexe sans cycle 
Il est connexe et comporte n-1 arêtes.
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. 
Un graphe biparti G = (X ,U ) est un graphe dont l'ensemble X des sommets peut être partitionné en 2 parties Y et Y' telles que tout arc a une extrémité dans Y et l'autre dans Y'.
• Un graphe est dit planaire si on peut le représenter dans le plan de telle sorte que les sommets soient des points distincts et que les arêtes ne s'intersectent pas. 
Home » , , , » Cours des Graphes - Recherche Operationnnelle

Membres