Skiena のアルゴリズムの本からの質問:
G が連結無向グラフであるとします。削除するとグラフが切断されるエッジ e は、ブリッジと呼ばれます。すべてのブリッジ e は、G の深さ優先探索ツリーのエッジである必要がありますか?
これまでの私の解決策（提案が必要です）：
カットノードを削除するとグラフが切断されるため、そのエッジを削除するとグラフも切断されるため、ブリッジは端の頂点がカットノードであるエッジであると思います。DFS 検索ツリーのエッジはツリー エッジとバック エッジであり、バック エッジの削除によってグラフが切断されないため、ツリー エッジのみがカット エッジ (またはブリッジ) になることができます。
基本的に、はい。ただし、いくつかの発言があります。
カットノードを削除するとグラフが切断されるため、そのエッジを削除するとグラフも切断されるため、ブリッジは端の頂点がカットノードであるエッジであると思います。
これは正確ではありません。特に、(ブリッジ => エッジにカット ノードがある) と読むと、そのとおりです。しかし、「ブリッジとは端点が頂点であるエッジである...」という表現は、逆の含意を示唆していますが、これは真実ではありません。全体として、この文は残りの議論にはほとんど関係がないので、省略します。
...バックエッジの削除はグラフを切断しないため、ツリーエッジのみがカットエッジ（またはブリッジ）になることができます。
ええ、それだけです。さらに、DFS は接続されたグラフのすべての頂点 (またはすべてのエッジにラベルを付ける) を探索することに注意する必要があります。