Graphe connexe

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Graphe connexe.
Graphe non connexe, avec trois composantes connexes.

En théorie des graphes, un graphe non orienté est dit connexe s'il est d'un seul tenant.

Définitions[modifier | modifier le code]

Un graphe non orienté est dit connexe si quels que soient les sommets et de , il existe une chaîne reliant à .

Un sous-graphe connexe maximal d'un graphe non orienté quelconque est une composante connexe de ce graphe.

Pour un graphe orienté, on parle de connexité si en oubliant l'orientation des arêtes, le graphe est connexe. On parle de forte connexité s'il existe un chemin orienté depuis tout nœud u vers tout nœud v.

Propriétés[modifier | modifier le code]

  • Une composante connexe d'un graphe est un sous-graphe connexe de ce graphe.
  • Un graphe dont toutes les composantes connexes sont des arbres est une forêt.
  • Un graphe connexe à sommets possède au moins arêtes.
  • Un graphe connexe à sommets ayant exactement arêtes est un arbre.
  • Un graphe à sommets avec composantes connexes possède au moins arêtes.

Algorithmes[modifier | modifier le code]

L’algorithme de parcours en profondeur permet de déterminer si un graphe est connexe ou non. Dans le cas d'un graphe construit de façon incrémentale, on peut utiliser des algorithmes de connexité basés sur des pointeurs pour déterminer si deux sommets sont dans la même composante connexe.

Voir aussi[modifier | modifier le code]