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.