今日は、グラフでの関節点と橋について学びました（基本的に無向）。
私が読んだテキスト（スティーブン・ハリムの本）には、
私たちが頂点
uにvいてその隣にいるとき、もしdfs_low(v) >= dfs_num(u)それuがカット頂点です。
一方 、
dfs_low(v) > dfs_num(u)ブリッジチェック中の状態になります。
しかし、2番目のケース(ブリッジ)から平等がなくなった理由がわかりません。これで私を助けてください。
PS: dfs_num(i)dfs で見られるように頂点に番号を付けます。
dfs_low(i)親以外の i から到達可能な最小番号の頂点を示します。
u は関節点であるが、uv はブリッジではないと考えられる状況を想定してください。次に、uvリンク以外のvからuへのパスが存在します。したがって、u を含む二重接続コンポーネントから v を含むコンポーネントに渡される DFS は、最終的に再び u に到達し、 の等式を提供しdfs_low(v) >= dfs_num(u)ます。(不等式の大なり部分は、u がアーティキュレーション ポイントであるため発生します。そのため、v からのパスは、u を通過しないと番号の小さい頂点に到達できず、DFS はそのようなパスをたどりません。)
しかし、uv もブリッジである場合、v と u の間にブリッジ uv 以外のパスは存在しません。したがって、DFS は二度とあなたに到達しません。DFS が v に達した後のすべてのdfs_num値は、厳密に よりも大きくなりdfs_num(u)ます。