algorithm - 深さ優先検索に関する懸念

Question

G が無向連結グラフの場合、その各辺は深さ優先探索木に含まれているか、バック エッジであることを証明してください。

さて、直感とスティーブン・スキーナによる授業での講義から、私は上記のことが当てはまることを知っています。また、DFS が周期を見つけるのに優れていることも知っています。

ただし、ここでの問題は、エッジがツリー エッジまたはバック エッジであることを「証明」する方法がわからないことです。

Answer 1

(理論上) 可能な 4 つのケースを考えてみましょう。エッジには次のものがあります。

1. 木の端
2. バックエッジ
3. 木の端と後ろの端の両方
4. 木の端でも後ろの端でもない

何が必要かを証明するには、ケース 3 と 4 が起こりえないこと、つまり矛盾につながることを示す必要があります。