Ouvrir le menu principal
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.

Sommaire

DéfinitionsModifier

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ésModifier

  • 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.

AlgorithmesModifier

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.

Complexité théoriqueModifier

On s'intéresse à savoir si un graphe non orienté est connexe. Dès 1979, on savait qu'il était dans une classe probabiliste en espace logarithmique[1]. Reingold, dans un article de 2008, a démontré que le problème d'accessibilité dans un graphe non orienté est dans LOGSPACE[2], donc savoir si un graphe est connexe est aussi dans LOGSPACE. Par contre, le problème d'accessibilité dans un graphe sans cycle est dans NC1 (voir NC), car il suffit de vérifier que le nombre d'arêtes. Quand on présente le graphe comme une union de cycles, le problème est NC1-complet[3].

Notes et référencesModifier

  1. Romas Aleliunas, Richard M. Karp, Richard J. Lipton et Laszlo Lovasz, « Random Walks, Universal Traversal Sequences, and the Complexity of Maze Problems », Proceedings of the 20th Annual Symposium on Foundations of Computer Science, IEEE Computer Society, série SFCS '79,‎ , p. 218–223 (DOI 10.1109/SFCS.1979.34, lire en ligne, consulté le 30 mai 2019)
  2. Omer Reingold, « Undirected connectivity in log-space », Journal of the ACM, vol. 55, no 4,‎ , p. 1–24 (lire en ligne)
  3. Stephen A Cook et Pierre McKenzie, « Problems complete for deterministic logarithmic space », Journal of Algorithms, vol. 8, no 3,‎ , p. 385–394 (ISSN 0196-6774, DOI 10.1016/0196-6774(87)90018-6, lire en ligne, consulté le 30 mai 2019)

Voir aussiModifier