3

関節頂点を見つける際のルート カット ノード、ブリッジ カット ノード、親カット ノードとは何ですか? 誰かが例を挙げて説明してくれませんか。特にブリッジカットノードと混同しています。その定義は言う

v から最も早く到達可能な頂点が v の場合、単一のエッジ (parent[v], v) を削除するとグラフが切断されます

v から最も早く到達可能な頂点はどのようにして v になるのでしょうか?

4

1 に答える 1

6

あなたがまだ気にしているかどうかはわかりませんが、私は今同じテキストを読んでいます

ルート カット ノード

ルートカットノードはかなり明白だと思います

ブリッジカットノード

v の reachable_ancestor を変更することを忘れないでください。次の 3 つの条件を満たす必要があります。

  • バックエッジであるエッジ (v, y) がある
  • エッジ (v, y) の場合、y は v の親ではありません
  • y の entry_time は、v の reachable_ancestor の entry_time より前です

したがって、本の図 5.13 を見ると、1 つの (ツリーの下の方にある) ブリッジ カット ノードには y 以外の親がないため、reachable_ancestor が最初の reachable_ancestor[v ] = v. これにより、その親がブリッジ カット ノードになり、(リーフではないという理由だけで) そのノードもブリッジ カット ノードになります。

親カットノード

図 5.13 で v の親が (ブリッジ カット ノードではなく) 親カット ノードである理由は、ブリッジが次の条件を満たす必要があるためです。

  • 縁は木の縁
  • v 以下から y 以上に接続するバック エッジはありません

明らかに、グラフでは、v の子はその親 (y) とその上に接続しており、v と y の間のエッジをブリッジではなく、y をカットノードにしています。

それが役に立ったことを願っています！

于 2013-05-10T14:48:02.960 に答える