Chaque pont d'un graphique est-il un bord dans l'arborescence de recherche DFS?

Question

Une question du livre d'algorithme de Skiena:

Supposons que G est un graphe non orienté connecté. Un bord e dont la suppression déconnecte le graphe est appelé un pont. Est-ce que chaque bridge doit être un bord dans un arbre de recherche en profondeur de G?

Ma solution à ce jour (besoin de suggestions):

Je pense que le pont est une arête dont le sommet final est un noeud de coupe, car la suppression du noeud de coupe débranche le graphique afin de retirer ce bord déconnectera également le graphique. Les arêtes dans l'arborescence de recherche DFS sont les arêtes arrière & et seules les arêtes d'arbre peuvent être des arêtes coupées (ou des ponts) car le retrait du bord arrière ne déconnecte pas le graphique.

Answer 1

Fondamentalement, oui. J'ai quelques remarques cependant:

Je pense que le pont est une arête dont le sommet final est un noeud de coupe, car la suppression du noeud de coupe débranche le graphique afin de retirer ce bord déconnectera également le graphique.

Ceci n'est pas exact. En particulier, si vous le lisez comme (bridge => edge a un noeud coupé), c'est vrai. Mais formulé comme "un pont est un bord dont le sommet fin ...", il suggère l'implication inverse, ce qui n'est pas vrai. Dans l'ensemble, cette phrase est en grande partie hors de propos pour le reste de l'argument et je l'omettrais simplement.

... seuls les arêtes de l'arbre peuvent être des arêtes coupées (ou des ponts) car le retrait du bord arrière ne déconnecte pas le graphique.

Ouais, c'est ça. De plus, vous devez noter que DFS explore tous les sommets (ou les étiquettes de tous les bords) d'un graphe connexe. Vous ne pourriez pas dire que si vous assumez le contraire, alors DFS ne visiterait pas tous les nœuds?