Discussion :

[dvp_zero]

Bonjour à tous,

j'aimerai connaitre le nombre de points d'articulation de mon graphe de manière automatique.

Existe-t-il un algorithme capable de compter le nombre de points d'articulation dans un graphe quelconque?

Merci d'avance.

[Acrim]

Je pense que tu devrais trouver en partie ton bonheur ici.

[dvp_zero]

Merci beaucoup

[dvp_zero]

Bonjour à tous,

je suis occupé à lire l'article en fichier attaché et je rencontre une difficulté de compréhension au niveau de la mise à jour du paramètre back[v] (page 6).

Les auteurs distinguent deux cas mais je ne comprends pas très bien cette distinction. Dans un cas il met à jour back[w] et de l'autre back[v].

A quel moment faut-il mettre jour cette valeur? Lors d'un deuxième passage sur l'arbre? A quoi correspond le backtrack par rapport au back-edge?

Merci beaucoup

[Acrim]

Je n'arrive pas a ouvrir le fichier joint mais j'imagine qu'il s'agit de celui là.



Si cela t’intéresse il y a un exemple ici. Par rapport au vocabulaire le "back-edge" correspond à un arc allant du nœud visité vers un nœud déjà visité (placé donc plus haut dans l'arbre formé par le parcours du graphe). C'est la présence de cet arc qui révéle l’existence d'une deuxième chemin. Le backtrack quant à lui correspond au fait de remonter pour considérer un autre sous arbre lorsqu'on est arrivé au bout d'une branche.

[dvp_zero]

Oui il s'agit bien de ton fichier.

Merci beaucoup pour la présentation que tu m'as donné. L'exemple est très bien fait.

Et donc si j'ai bien compris, la phase qu'ils appellent case 1 dans le fichier s'effectue lors de la descente dans l'arbre (donc dans la descente lors de la récursion) et le case 2 s'effectue lors de la remonté dans la récursion, d'où backtracking c'est bien ça?

Un très grand merci.

[dvp_zero]

Comme l'algorithme dépend du parcours en profondeur pour trouver le nombre de points d'articulation, est-ce que le sommet de départ joue une importance dans le résultat final?

Ou alors quelque soit le sommet de départ choisit pour le parcours en profondeur on trouvera tous les points d'articulation?

J'aurais tendance à dire que le sommet de départ importe peu mais j'aimerai être sur...

Merci

[Acrim]

Non le sommet de départ n'est pas important. Cependant, il a un traitement un peu particulier du fait qu'il ne peut pas y avoir d'arc retour (si il a plus d'un fils alors c'est un point d'articulation).

[dvp_zero]

Cependant, il a un traitement un peu particulier du fait qu'il ne peut pas y avoir d'arc retour (si il a plus d'un fils alors c'est un point d'articulation).

S'il a plus d'un fils dans l'arbre obtenu par le parcours en profondeur alors je suppose?

Parce que dans l'exemple de la présentation (c.f message 28/04/2011 12h07), le noeud 1 dans le graphe n'est pas un point d'articulation mais possède 2 fils dans le graphe.
Pourrais-tu m'expliquer l'intuition pour le cas particulier du noeud de départ? parce que j'arrive pas à comprendre.

Merci

[Acrim]

Oui je parlais du nœud de départ dans l'arbre construit par le DFS.

L'explication est assez simple : la racine est un point d'articulation c'est un passage obligé pour passer d'un groupe de nœuds A à un autre groupe de nœuds B (pour paraphraser la définition du point d'articulation). Ainsi quand le DFS va explorer les nœuds appartenant au groupe A il ne trouvera aucun arc pour rejoindre les nœuds du groupe B. Pour les atteindre il faudra que le DFS reparte du nœud racine.

C'est pas très technique comme explication mais ça devrait te permettre de comprendre

[dvp_zero]

Oui j'ai compris maintenant.

Un très grand merci pour tes explications