Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, un graphe non orienté est dit connexe s'il est d'un seul tenant.
Cet article est une ébauche concernant les mathématiques.
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 dit qu'il est :
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.
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. Quand on présente le graphe comme une union de cycles, le problème est NC1-complet[3].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.
