二重連結成分

グラフ理論では、2連結成分またはブロック（ 2連結成分とも呼ばれる）は、最大2連結部分グラフです。連結グラフは、グラフのブロックカット木と呼ばれる2連結成分のツリーに分解されます。ブロックは、カット頂点、分離頂点、または連結点と呼ばれる共有頂点で互いに接続されています。具体的には、カット頂点とは、削除すると連結成分の数が増加する頂点のことです。^[1]カット頂点を最大で1つ含むブロックはリーフブロックと呼ばれ、ブロックカット木のリーフ頂点に対応します。

アルゴリズム

線形時間深さ優先探索

連結無向グラフの2連結成分を計算するための古典的な逐次アルゴリズムは、ジョン・ホップクロフトとロバート・タージャン（1973）によるものです。 ^{[2]このアルゴリズムは}線形時間で実行され、深さ優先探索に基づいています。このアルゴリズムは、『アルゴリズム入門』（第2版と第3版の両方）の問題22-2としても概説されています。

アイデアは、次の情報を維持しながら深さ優先検索を実行することです。

深さ優先探索木の各頂点の深さ（一度訪問すると）、および
各頂点 $v$ について、深さ優先探索木における $v$ のすべての子孫（ $v$ 自身を含む）の近傍の最も低い深さを $ローポイント$ と呼びます。

深さは、深さ優先探索中に維持される標準です。 $vのローポイントは、$ $v$ のすべての子孫を訪問した後(つまり、 $v が$ 深さ優先探索スタックからポップされる直前)、 $v$ の深さ、 $v$ のすべての隣接要素(深さ優先探索ツリー内の $v$ の親以外) の深さ、および深さ優先探索ツリー内の $vのすべての子のローポイントの最小値として計算できます。$

重要な事実は、非ルート頂点 $vが、$ $lowpoint($ $y$ $) \geq depth($ $v$ )となるような $v$ の子 $yが存在する場合のみ、2 つの 2 重連結コンポーネントを分離するカット頂点 (または連結点$ $)$ であるということです。この特性は、深さ優先探索が $vのすべての子から返されたら (つまり、$ $v$ が深さ優先探索スタックからポップされる直前に) テストでき、 trueの場合、 $v はグラフを異なる 2 重連結コンポーネントに分割します。これは、そのような$ $y$ から 1 つの 2 重連結コンポーネントを計算し( $y を$ 含むコンポーネントには、 $y$ のサブツリーと $v$ が含まれます)、次にツリーから $y$ のサブツリーを消去することで表すことができます。

ルート頂点は個別に処理する必要があります。ルート頂点は、DFS ツリーに少なくとも 2 つの子がある場合にのみカット頂点になります。したがって、ルートの各子サブツリー (ルートを含む) から 1 つのコンポーネントを構築するだけで十分です。

擬似コード

GetArticulationPoints(i, d)
    訪問[i] := true
    深さ[i] := d
    低い[i] := d
    子の数:= 0
    アーティキュレーション:= false

    adj[i]内の各niについて、訪問されていない場合は[ni]を実行する
         
            親[ni] := i
            アーティキュレーションポイントを取得します(ni, d + 1)
            子の数:=子の数+1
            low[ni] ≥ depth[i]の場合、 
                isArticulation := true
            low[i] := 最小値 (low[i], low[ni])
        そうでない場合、 ni ≠ parent[i]ならば
            low[i] := 最小値 (low[i], 深さ[ni])
    (parent[i] ≠ null かつisArticulation)または(parent[i] = null かつchildCount > 1)の場合
        iをアーティキュレーションポイントとして出力

子と親という用語は、元のグラフではなく、DFS ツリー内の関係を表すことに注意してください。

カット頂点を見つけるための Tarjan アルゴリズムのデモ。Dは深さ、**L は**最低点を表します。

その他のアルゴリズム

上記のアルゴリズムの単純な代替法は、連鎖分解を使用するもので、これはDFS木に依存する特別な ear 分解です。^{[3]連鎖分解は、この}走査規則によって線形時間で計算できます。 $C を$ $G$ の連鎖分解とします。このとき、 $G$ が 2 頂点連結であるためには、 $G$ の最小次数が2 であり、 $C 1 が$ $C$ 内の唯一の閉路である必要があります。これにより、直ちに線形時間の 2 連結性テストが得られ、次のステートメントを使用して線形時間で $G$ のすべてのカット頂点をリストするように拡張できます。連結グラフ $G$ (最小次数 2)の頂点 $vは、$ $v が$ ブリッジに接続されているか、 $vが$ $C$ $-$ $C$ $1$ 内の閉路の最初の頂点である場合に限り、カット頂点です。カット頂点のリストを使用して、線形時間で $G$ のブロックカット木を作成できます。

この問題のオンライン版では、頂点と辺は動的に追加され（削除はされない）、データ構造は二重連結成分を維持する必要があります。Jeffery WestbrookとRobert Tarjan（1992）^[4]は、分離集合データ構造に基づいてこの問題の効率的なデータ構造を開発しました。具体的には、 $n$ 個の頂点追加と $m個の辺追加を合計時間$ $O (mα (m 、 n))$ で処理します。ここで、 $αは$ 逆アッカーマン関数です。この時間制限は最適であることが証明さ $れ$ ています。

Uzi VishkinとRobert Tarjan (1985) ^[5]は、 $n$ $+$ $m個のプロセッサで$ $O$ $(log$ $n$ $)$ 時間で実行されるCRCW PRAM上の並列アルゴリズムを設計しました。

関連構造

同値関係

任意の無向グラフの辺に関する二項関係を定義できます。この関係によれば、2 つの辺 $e$ と $f は、$ $e = f$ であるか、グラフが $e$ と $f の$ 両方を通る単純閉路を含む場合のみ関連しています。すべての辺は自身と関連しており、辺 $e が別の辺$ $f$ と関連するのは、 $f が$ $e$ と同じように関連している場合のみです。わかりにくいですが、これは推移的な関係です。つまり、辺 $e$ と $f を$ 含む単純閉路と、辺 $f$ と $g を$ 含む別の単純閉路が存在する場合、これら 2 つの閉路を組み合わせて、 $e$ と $g$ を通る単純閉路を見つけることができます。したがって、これは同値関係であり、これを使用して、辺を同値クラスに分割できます。同値クラスとは、2 つの辺が同じ同値クラスに属する場合にのみ、それらの辺が互いに関連するという特性を持つ辺のサブセットです。各同値クラスの辺によって形成されるサブグラフは、指定されたグラフの 2 連結コンポーネントです。したがって、2 連結コンポーネントはグラフの辺を分割しますが、頂点を共有する場合があります。^[6]

ブロックグラフ

与えられたグラフ $G$ のブロックグラフは、そのブロックの交差グラフである。したがって、ブロックグラフは $G$ の各ブロックに対して 1 つの頂点を持ち、対応する 2 つのブロックが頂点を共有する場合は常に 2 つの頂点の間に辺を持つ。グラフ $H が別のグラフ$ $G$ のブロックグラフとなるのは、 $H$ のすべてのブロックが完全なサブグラフである場合である。この特性を持つグラフ $Hは$ ブロックグラフとして知られている。^[7]

ブロックカットツリー

グラフ $Gの$ カットポイント、カット頂点、またはアーティキュレーションポイントは、2 つ以上のブロックによって共有される頂点です。連結グラフのブロックとカットポイントの構造は、ブロックカットツリーまたはBC ツリーと呼ばれるツリーで記述できます。このツリーには、指定されたグラフの各ブロックと各アーティキュレーションポイントの頂点があります。ブロックカットツリーには、ブロックとそのブロックに属するアーティキュレーションポイントの各ペアごとにエッジがあります。^[8]

参照

注記

^ AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). 「3. グラフ理論」.グラフとネットワーク分析のためのPython . SPRINGER. ISBN 978-3-319-85037-5. OCLC 1047552679。カット頂点とは、削除するとネットワークコンポーネントの数が増加する頂点です。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)
^ Hopcroft, J.; Tarjan, R. (1973). 「アルゴリズム447: グラフ操作のための効率的なアルゴリズム」Communications of the ACM . 16 (6): 372–378. doi : 10.1145/362248.362272 .
^ Schmidt, Jens M. (2013)、「2頂点および2辺の連結性に関する簡単なテスト」、Information Processing Letters、113 (7): 241–244、arXiv : 1209.0700、doi :10.1016/j.ipl.2013.01.016。
^ Westbrook, J.; Tarjan, RE (1992). 「ブリッジ接続コンポーネントとバイコネクトコンポーネントのオンライン維持」Algorithmica . 7 (1–6): 433–464. doi :10.1007/BF01758773.
^ タージャン、R.;ヴィシュキン、U. (1985)。「効率的な並列双接続性アルゴリズム」。サイアム J. コンピューティング。 14 (4): 862–874。CiteSeerX 10.1.1.465.8898。土井：10.1137/0214061。
^ Tarjan & Vishkin (1985) はこの同値関係の定義を Harary (1969) に帰しているが、Harary はそれを明示的に説明していないようだ。
^ ハラリー、フランク（1969）、グラフ理論、アディソン・ウェズレー、p. 29。
^ ハラリー（1969）、36ページ。

参考文献

Eugene C. Freuder (1985). 「バックトラック制限検索のための十分条件」Journal of the Association for Computing Machinery . 32 (4): 755–761. doi : 10.1145/4221.4225 .

外部リンク

双連結成分の C++ 実装

[AL-TAIE_p.-1] AL-TAIE, MOHAMMED ZUHAIR. KADRY, SEIFEDINE (2019). 「3. グラフ理論」.グラフとネットワーク分析のためのPython . SPRINGER. ISBN 978-3-319-85037-5. OCLC 1047552679。カット頂点とは、削除するとネットワークコンポーネントの数が増加する頂点です。{{cite book}}: CS1 maint: 複数の名前: 著者リスト (リンク)

[2] Hopcroft, J.; Tarjan, R. (1973). 「アルゴリズム447: グラフ操作のための効率的なアルゴリズム」Communications of the ACM . 16 (6): 372–378. doi : 10.1145/362248.362272 .

[Schmidt-3] Schmidt, Jens M. (2013)、「2頂点および2辺の連結性に関する簡単なテスト」、Information Processing Letters、113 (7): 241–244、arXiv : 1209.0700、doi :10.1016/j.ipl.2013.01.016。

[4] Westbrook, J.; Tarjan, RE (1992). 「ブリッジ接続コンポーネントとバイコネクトコンポーネントのオンライン維持」Algorithmica . 7 (1–6): 433–464. doi :10.1007/BF01758773.

[5] タージャン、R.;ヴィシュキン、U. (1985)。「効率的な並列双接続性アルゴリズム」。サイアム J. コンピューティング。 14 (4): 862–874。CiteSeerX 10.1.1.465.8898。土井：10.1137/0214061。

[6] Tarjan & Vishkin (1985) はこの同値関係の定義を Harary (1969) に帰しているが、Harary はそれを明示的に説明していないようだ。

[7] ハラリー、フランク（1969）、グラフ理論、アディソン・ウェズレー、p. 29。

[8] ハラリー（1969）、36ページ。