Loading AI tools
De Wikipédia, l'encyclopédie libre
En théorie des graphes, une composante fortement connexe d'un graphe orienté G est un sous-graphe de G possédant la propriété suivante, et qui est maximal pour cette propriété : pour tout couple (u, v) de nœuds dans ce sous-graphe, il existe un chemin de u à v.
Cet article est une ébauche concernant les mathématiques et l’informatique théorique.
Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.
Un graphe est dit fortement connexe s'il est formé d'une seule composante fortement connexe. De manière générale, un graphe se décompose de manière unique comme union de composantes fortement connexes deux à deux disjointes.
Le graphe H des composantes fortement connexes de G est défini de la manière suivante :
Le graphe des composantes fortement connexes est un graphe orienté toujours acyclique. Inversement, tout graphe acyclique est isomorphe au graphe de ses composantes fortement connexes.
Plusieurs algorithmes permettent de calculer la décomposition en composantes fortement connexes d'un graphe en temps linéaire :
Certains algorithmes utilisent la décomposition en composantes fortement connexes comme une première étape, c'est le cas par exemple d'un algorithme pour le problème 2-SAT[2].
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.
