Demande d'aide : sommet important dans une CF
nickz34
-
Utilisateur anonyme -
Utilisateur anonyme -
Bonjour à tous, je cherche une méthode qui me permet de trouver un sommet important dans une composante fortement connexe.
Un sommet important dans une CFC est un sommet qui quand il est supprimé, fait perdre la caractère fortement connexe à la composante à laquelle il appartient.
Je n'ai pas trouvé d'explication sur une telle méthode sur Google.
Merci d'avance
Un sommet important dans une CFC est un sommet qui quand il est supprimé, fait perdre la caractère fortement connexe à la composante à laquelle il appartient.
Je n'ai pas trouvé d'explication sur une telle méthode sur Google.
Merci d'avance
5 réponses
Hello,
Voici deux documents qui je pense vont t'éclairer.
https://www.irif.fr/~jep//PDF/TCJava/XJava9.pdf
http://cristal.inria.fr/~levy/x/tc/polycopie-1.6/main009.html
On constate dans les deux cas que la recherche des points d'articulation est la clef.
Voici deux documents qui je pense vont t'éclairer.
https://www.irif.fr/~jep//PDF/TCJava/XJava9.pdf
http://cristal.inria.fr/~levy/x/tc/polycopie-1.6/main009.html
On constate dans les deux cas que la recherche des points d'articulation est la clef.
J'avais pas tilté le rapprochement entre point d'articulation pour une composante connexe d'un graphe non orienté et pour une CFC d'un graphe orienté.. Je me sens bête.
Merci BugCrusher
Merci BugCrusher
Vraiment pas de quoi, et ne te sens pas bête, tu travailles sur des choses pas complètement intuitives :o)
J'ai du mal à comprendre comment ils affectent la valeur bleue à la page 10 du Xjava9.pdf. Autant la rouge je comprend (quand on atteint le sommet u dans le parcours en prof)
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question