グラフにおける橋(bridge)を検出するアルゴリズム

2020年2月15日グラフグラフ, 競プロ, 関節点, 切断点, , lowlink, DFS

無向連結グラフにおいて、「取り除いたときにグラフ全体が非連結になるような辺」をと言います。

※「連結」とは任意の2頂点間を行き来できることを言い、「非連結」は逆に行き来できない頂点があることを言います。(くわしくはグラフを参照)

以下の図の赤い部分が「橋」の例です。

橋の例

元々が連結でない無向グラフについては、「取り除いたときに非連結成分の数が増える辺」を橋とします。

アルゴリズム

単純なアルゴリズム:

  1. 全ての辺 e に対して以下を実行する
    1. e をグラフから取り除く
    2. グラフが非連結かを確認する(幅優先探索か深さ優先探索で確認ができます)。非連結なら e は橋
    3. e をグラフに戻す

※ 辺を取り除いてみてグラフが非連結になるかどうかを、全ての辺について確かめれば良いです。

Union-Find Tree を用いた単純なアルゴリズム:

  1. 全ての辺 e1=(u1,v1) に対して以下を実行する
    1. e1 以外の全ての辺 e2=(u2,v2) について以下を実行する
      1. u2 と v2 を Union-Find Tree 上の同じ集合にまとめる (unite)
    2. u1 と v1 が同じ集合になければ、e1 を除いたグラフは非連結で、e1 は橋

※ Union-Find Tree についてはこちらを参照
※ こちらも辺を取り除いてみてグラフが非連結になるかどうかを、全ての辺について確かめれば良いです。

lowlink を用いた効率的なアルゴリズム:

  1. 適当な頂点から、DFS で以下を計算する
    • ord[u] : DFS で頂点 u を何番目に探索したか
    • low[u] : u からの後退辺を高々1回まで用いて到達できる頂点 w について、ord[w] の最小値
  2. 以下の条件を満たす辺 (u,v) が橋(bridge)
    • ord[u] < low[v]

※ DFS tree (深さ優先探索木)は、DFSでグラフを探索する際に通る辺や頂点の集合のことです。これは木になっています。

※ 上述のアルゴリズムは、以下の「 (u,v) が橋となる条件」が元になっています。

  1. u が子として以下を満たす頂点 v を持つ
    • v を根とする DFS tree の部分木において、u や u の祖先への後退辺を持つ頂点が存在しない

※ ある点 u が関節点(Articulation Points)であるときは以下のどちらかを満たします。

  1. u が DFS tree の根(root) で、子が2つ以上存在する
  2. u が DFS tree の根(root) でなく、頂点 u のある子 v について ord[u] ≤ low[v] を満たす

計算量

  • 単純なアルゴリズム:O(V(V+E))
  • lowlink を用いたアルゴリズム:O(V+E)

※ Union-Find Tree を用いたアルゴリズムは、O(V(V+E)) と微妙に異なりますがほとんど変わりません。

C++での実装例

グラフ上の橋の意味

グラフをネットワークとして考えると、橋はネットワーク上の脆弱性を表現しています。その辺に障害が発生して使えなくなると、ネットワークが非連結になってしまい問題となります。

よって、ネットワークの信頼性などを考慮する上で、「橋」という概念が用いられます。

練習問題