連結性（グラフ理論）

数学とコンピュータサイエンスにおいて、連結性はグラフ理論の基本概念の1つです。連結性とは、残りのノードを2つ以上の独立したサブグラフに分割するために削除する必要のある要素（ノードまたはエッジ）の最小数を求めるものです。^[¹^]これはネットワークフロー問題の理論と密接に関連しています。グラフの連結性は、ネットワークとしての回復力の重要な尺度です。

接続された頂点とグラフ

無向グラフ $G$ において、頂点 $u$ と $v は、$ $Gに$ $u$ から $v$ へのパスが存在する場合、接続されていると呼ばれます。そうでない場合、それらは切断されていると呼ばれます。さらに、2 つの頂点が長さ $1$ のパスによって接続されている場合(つまり、それらが単一のエッジの端点である場合)、それらの頂点は隣接していると呼ばれます。

グラフは、グラフ内のすべての頂点のペアが連結している場合に連結であると言われます。これは、すべての頂点のペア間にパスが存在することを意味します。連結していない無向グラフは非連結と呼ばれます。したがって、無向グラフ $Gは、$ $G$ 内に2つの頂点が存在し、これらの頂点を終点とするパスが存在しない場合に非連結です $。$ 頂点が1つだけのグラフは連結です。頂点が2つ以上ある辺のないグラフは非連結です。

有向グラフは、その有向エッジをすべて無向エッジに置き換えると連結（無向）グラフになる場合、弱連結と呼ばれます。任意の頂点ペア $u$ $、$ $vに対して、$ $uから$ $v$ への有向パスまたは v から $u$ への有向パスが含まれる場合、単側連結または単側（半連結とも呼ばれる）です。^[²^]任意の頂点ペア $u$ $、$ $v$ に対して、 $uから$ $v$ への有向パスと $vから$ $u$ への有向パスが含まれる場合、強連結または単に $強$ 連結です。

構成要素とカット

連結成分とは、無向グラフにおける最大の連結部分グラフのことである。各頂点は必ず1つの連結成分に属し、各辺も同様である。グラフが連結であるのは、連結成分がちょうど1つだけ存在する場合に限る。

強連結成分とは、有向グラフにおける最大の強連結部分グラフのことである。

連結グラフ $G$ の頂点カットまたは分離集合とは、それを取り除くと $G$ が非連結になる頂点の集合のことです。頂点連結度 $κ$ $($ $G$ $) ($ $Gが$ 完全グラフでない場合) は、最小の頂点カットのサイズです。頂点連結度が $k$ 以上の場合、そのグラフは $k$ 頂点連結または $k$ 連結と呼ばれます。

より正確には、任意のグラフ $G$ (完全グラフであるか否かを問わず) は、少なくとも $k$ $+ 1個の頂点を含み、かつ、その頂点の削除によって$ $グラフ$ が分断される $k$ $- 1$ 個の頂点の集合を含まない場合に、k 頂点連結であると言われます。また、 $κ$ $($ $G$ $) は、$ $G$ が $k$ 連結となる最大の $k$ として定義されます。特に、 $n$ 個の頂点を持つ完全グラフ $K$ $n$ は、頂点カットを全く持ちませんが、 $κ$ $($ $K$ $n$ $) =$ $n$ $- 1$ です。

2 つの頂点 $u$ と $v$ の頂点カットとは、グラフから削除すると $u$ と $v$ が切断される頂点の集合のことです。局所連結性 $κ$ $($ $u$ $,$ $v$ $)は、$ $u$ と $v$ を分離する最小の頂点カットのサイズです。局所連結性は無向グラフに対して対称です。つまり、 $κ$ $($ $u$ $,$ $v$ $) =$ $κ$ $($ $v$ $,$ $u$ $)$ です。さらに、完全グラフを除いて、 $κ$ $($ $G$ $)$ は、隣接しないすべての頂点ペア $u$ $、$ $vに対する$ $κ$ $($ $u$ $,$ $v$ $)$ の最小値に等しくなります。

$2連結性は$ 双連結性とも呼ばれ、 $3連結性は$ 三連結性とも呼ばれる。連結ではあるが $2$ 連結ではないグラフ $Gは、$ 分離可能と呼ばれることもある。

エッジについても同様の概念を定義できます。単一の特定のエッジを切断するとグラフが分断される単純なケースでは、そのエッジはブリッジ $と呼ばれます。より一般的には、 G$ のエッジカットとは、それを取り除くとグラフが分断されるエッジの集合です。エッジ連結度 $λ (G)$ は最小のエッジカットのサイズであり、 2 つの頂点 $u$ $、$ $v$ の局所エッジ連結度 $λ (u 、 v)は、$ $u$ と $v$ を分断する最小のエッジカットのサイズです。ここでも、局所エッジ連結度は対称です。エッジ連結度が $k$ 以上の場合、グラフは $k$ エッジ連結であると呼ばれます。

グラフは、連結度が最小次数に等しい場合に最大連結であると言われます。グラフは、辺連結度が最小次数に等しい場合に最大辺連結であると言われます。 ^[³^]

超接続性とハイパー接続性

グラフは、最小頂点カットによって頂点が分離される場合、超連結またはスーパーκであると言われる。グラフは、各最小頂点カットの削除によってちょうど2つの連結成分が生成され、そのうちの1つが孤立頂点である場合、ハイパー連結またはハイパーκであると言われる。グラフは、任意の最小頂点カットによってグラフがちょうど2つの連結成分に分割される場合、半ハイパー連結または半ハイパーκであると言われる。^{[ 4 ]}

より正確には、 $G$ 連結グラフは、すべての最小頂点カットが1つの（最小次数）頂点に隣接する頂点から構成される場合、超連結または超κであると言われます。G連結グラフは、すべての最小辺カットが何らかの（最小次数）頂点に接続する辺から構成される場合 $、$ 超辺連結または超λであると言われます。^{[ 5 ]}

$G$ のカットセット $Xは、$ $X が X$ $に含まれない任意の頂点$ $u$ の近傍 $N($ $u$ $)$ を含まない場合 $、$ 非自明なカットセットと呼ばれます。このとき、超連結性 $\displaystyle \kappa _{1}}$ $G$ の $\displaystyle \kappa _{1}(G)=\min\{|X|:X{\text{は非自明なカットセットである}}\}.}$

非自明なエッジカットとエッジ超接続性 $\lambda _{1}(G)$ も同様に定義される。^{[ 6 ]}

メンガーの定理

グラフの接続性に関する最も重要な事実の1つは、メンガーの定理であり、これは頂点間の独立した経路の数によってグラフの接続性と辺の接続性を特徴づけるものである。

$u$ と $v$ がグラフ $G$ の頂点である場合、 $u$ と $v$ の間のパスの集合は、 $u$ と $v$ 自身以外のどの 2 つのパスも頂点を共有しない場合に独立であると呼ばれます。同様に、集合内の $どの$ 2 つのパスも辺を共有しない場合に、辺独立であると呼ばれます。uと $vの間の相互に独立したパスの数は$ $κ'(u, v)$ と表記され、 $u$ と $v$ の間の相互に辺独立なパスの数は $λ'(u, v)$ と表記されます。

メンガーの定理は、異なる頂点u、vに対して、 $λ (u 、 v)は$ $λ'(u 、 v)$ に等しく、uがvに隣接していない場合は $κ (u 、 v)は$ $κ'(u 、 v)$ に等しいと主張している。^{[ 7 ]}^{[ 8 ]}この事実は実際には最大フロー最小カット定理の特殊なケースである。

計算上の側面

グラフ内の2つの頂点が接続されているかどうかを判定する問題は、幅優先探索などの探索アルゴリズムを用いることで効率的に解決できます。より一般的には、グラフが連結であるかどうか（例えば、非連結集合データ構造を用いるなど）を計算によって容易に判定したり、連結成分の数を数えたりすることができます。単純なアルゴリズムは、擬似コードで以下のように記述できます。

グラフ $G$ の任意のノードから開始します。
そのノードから、深さ優先探索または幅優先探索のいずれかを使用して処理を進め、到達したすべてのノードをカウントします。
$グラフ全体を走査した後、カウントされたノードの数がグラフG$ のノードの数と等しい場合、そのグラフは連結グラフであり、そうでない場合は非連結グラフである。

メンガーの定理によれば、連結グラフ $G$ における任意の2つの頂点 $u$ と $v$ について、 $κ$ $($ $u$ $,$ $v$ $)$ と $λ$ $($ $u$ $,$ $v$ $)は$ 最大フロー最小カットアルゴリズムを用いて効率的に求めることができる。そして、 $G$ の連結性と辺連結性は、それぞれ $κ$ $($ $u$ $,$ $v$ $)$ と $λ$ $($ $u$ $,$ $v$ $)$ の最小値として計算できる。

計算複雑性理論において、SLは、グラフ内の 2 つの頂点が接続されているかどうかを判定する問題にlog 空間で還元できる問題のクラスであり、これは2004 年にOmer ReingoldによってLと等しいことが証明されました。 ^[⁹^]したがって、無向グラフの接続性は $O(log$ $n$ $)$ 空間で解決できます。

ベルヌーイランダムグラフが連結している確率を計算する問題はネットワーク信頼性と呼ばれ、与えられた2つの頂点が連結しているかどうかを計算する問題はST信頼性問題と呼ばれます。これらのどちらも#P困難です。^{[ 10 ]}

接続されたグラフの数

n個のノードを持つ異なる連結ラベル付きグラフの数は、オンライン整数列百科事典に数列A001187として表されています。最初のいくつかの非自明な項は次のとおりです。

例

非連結グラフの頂点連結性と辺連結性はどちらも $0$ です。
$1$ 連結度は、少なくとも2つの頂点を持つグラフの連結度と同等である。
$n$ 個の頂点を持つ完全グラフの辺連結度は $n$ $-1である。n個$ $の$ 頂点を持つその他の単純グラフの辺連結度は、これより厳密に小さい。
木構造において、任意の異なる2つの頂点間の局所的な辺連結度は $1で$ ある。

接続性の制限

グラフの頂点連結度は、その辺連結度以下である。すなわち、 $κ (G) \leq λ (G)$ である。
少なくとも 2 つの頂点を持つグラフのエッジ連結度は、グラフの最小次数以下である。なぜなら、最小次数の頂点に接続するすべてのエッジを除去すると、その頂点がグラフの残りの部分から切り離されるからである。^{[ 1 ]}
$次数d$ の頂点推移グラフの場合、次のようになります。2 $($ $d$ $+ 1)/3 \leq$ $κ$ $($ $G$ $) \leq$ $λ$ $($ $G$ $) =$ $d$ 。^[¹¹^]
$次数d \leq 4$ の頂点推移グラフ、次数 $d$ の任意の (無向) 最小ケイリーグラフ、または次数 $d$ の任意の対称グラフの場合、両方の種類の連結性は等しくなります: $κ$ $($ $G$ $) =$ $λ$ $($ $G$ $) =$ $d$ 。^[¹²^]

その他の物件

グラフ準同型写像によって連結性が維持される。
$G$ が連結であれば、その線グラフ $L (G)$ も連結である。
グラフ $G$ が $2$ 辺連結であるのは、その向きが強連結である場合に限る。
バリンスキーの定理は、 $k$ 次元凸多面体の多面体グラフ( $1$ -スケルトン)は $k$ 頂点連結グラフであると述べている。 ^[¹³^]任意の 3 頂点連結平面グラフは多面体グラフであるというシュタイニッツの以前の定理(シュタイニッツの定理) は、部分的な逆を与えている。
GA Diracの定理によれば、グラフが $k$ $\geq 2で$ $k$ 連結である場合、グラフ内の任意の $k$ 個の頂点の集合に対して、その集合内のすべての頂点を通過するサイクルが存在する。 ^[¹⁴^]^[¹⁵^] $k$ $= 2$ の場合は逆が成り立つ。

参考文献

1 2 Diestel, R. (2005). "Graph Theory, Electronic Edition" . p. 12.
↑第11章：有向グラフ：有向グラフの双対性の原理：定義
↑グロス、ジョナサン L.、イェレン、ジェイ (2004)。グラフ理論ハンドブック。CRC Press。p . 335。ISBN 978-1-58488-090-5。
↑ Liu, Qinghai; Zhang, Zhao (2010-03-01). "The existence and upper bound for two types of restricted connectivity" . Discrete Applied Mathematics . 158 (5): 516– 521. doi : 10.1016/j.dam.2009.10.017 .
↑グロス、ジョナサン L.、イェレン、ジェイ (2004)。グラフ理論ハンドブック。CRC Press。p . 338。ISBN 978-1-58488-090-5。
↑ Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". Ars Combinatorica . 61 : 3– 22. CiteSeerX 10.1.1.101.1458 .
↑ギボンズ、A. (1985).アルゴリズム的グラフ理論.ケンブリッジ大学出版局.
↑長持博、茨木俊夫(2008).グラフ連結性のアルゴリズム的側面. ケンブリッジ大学出版局.
↑ Reingold, Omer (2008). "対数空間における無向連結性". Journal of the ACM . 55 (4): 1– 24. doi : 10.1145/1391289.1391291 . S2CID 207168478 .
↑ Provan, J. Scott; Ball, Michael O. (1983). "グラフが連結している確率を計算する際のカットのカウントの複雑さ". SIAM Journal on Computing . 12 (4): 777–788 . doi : 10.1137/0212053 . MR 0721012 . 。
↑ Godsil, C. ; Royle, G. (2001).代数的グラフ理論. Springer Verlag.
↑ Babai, L. (1996). Automorphism groups, isomorphism, reconstruction . Technical Report TR-94-10. University of Chicago. 2010-06-11 にオリジナルからアーカイブ済み。『組合せ論ハンドブック』第27章
↑ Balinski, ML (1961). " $n$ 空間における凸多面体のグラフ構造について" . Pacific Journal of Mathematics . 11 (2): 431– 434. doi : 10.2140/pjm.1961.11.431 .
↑ディラック、ガブリエル・アンドリュー(1960)。「4 つのグラフェンとその内容を抽象化します」。数学的表現。22 ( 1–2 ): 61– 85.土井: 10.1002/mana.19600220107。MR 0121311。。
↑ Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). " $k$ 連結グラフにおける $k個の$ 頂点を通るサイクルに関するディラックの定理の一般化" . Discrete Mathematics . 307 ( 7– 8): 878– 884. doi : 10.1016/j.disc.2005.11.052 . MR 2297171 . 。

[diestel-1] 1 2 Diestel, R. (2005). "Graph Theory, Electronic Edition" . p. 12.

[2] 第11章：有向グラフ：有向グラフの双対性の原理：定義

[3] グロス、ジョナサン L.、イェレン、ジェイ (2004)。グラフ理論ハンドブック。CRC Press。p . 335。ISBN 978-1-58488-090-5。

[4] Liu, Qinghai; Zhang, Zhao (2010-03-01). "The existence and upper bound for two types of restricted connectivity" . Discrete Applied Mathematics . 158 (5): 516– 521. doi : 10.1016/j.dam.2009.10.017 .

[5] グロス、ジョナサン L.、イェレン、ジェイ (2004)。グラフ理論ハンドブック。CRC Press。p . 338。ISBN 978-1-58488-090-5。

[6] Balbuena, Camino; Carmona, Angeles (2001-10-01). "On the connectivity and superconnectivity of bipartite digraphs and graphs". Ars Combinatorica . 61 : 3– 22. CiteSeerX 10.1.1.101.1458 .

[7] ギボンズ、A. (1985).アルゴリズム的グラフ理論.ケンブリッジ大学出版局.

[8] 長持博、茨木俊夫(2008).グラフ連結性のアルゴリズム的側面. ケンブリッジ大学出版局.

[9] Reingold, Omer (2008). "対数空間における無向連結性". Journal of the ACM . 55 (4): 1– 24. doi : 10.1145/1391289.1391291 . S2CID 207168478 .

[10] Provan, J. Scott; Ball, Michael O. (1983). "グラフが連結している確率を計算する際のカットのカウントの複雑さ". SIAM Journal on Computing . 12 (4): 777–788 . doi : 10.1137/0212053 . MR 0721012 . 。

[GandR-11] Godsil, C. ; Royle, G. (2001).代数的グラフ理論. Springer Verlag.

[12] Babai, L. (1996). Automorphism groups, isomorphism, reconstruction . Technical Report TR-94-10. University of Chicago. 2010-06-11 にオリジナルからアーカイブ済み。『組合せ論ハンドブック』第27章

[13] Balinski, ML (1961). " $n$ 空間における凸多面体のグラフ構造について" . Pacific Journal of Mathematics . 11 (2): 431– 434. doi : 10.2140/pjm.1961.11.431 .

[14] ディラック、ガブリエル・アンドリュー(1960)。「4 つのグラフェンとその内容を抽象化します」。数学的表現。22 ( 1–2 ): 61– 85.土井: 10.1002/mana.19600220107。MR 0121311。。

[15] Flandrin, Evelyne; Li, Hao; Marczyk, Antoni; Woźniak, Mariusz (2007). " $k$ 連結グラフにおける $k個の$ 頂点を通るサイクルに関するディラックの定理の一般化" . Discrete Mathematics . 307 ( 7– 8): 878– 884. doi : 10.1016/j.disc.2005.11.052 . MR 2297171 . 。

[

[

[

[ 4 ]

[ 5 ]

[ 6 ]

[ 7 ]

[ 8 ]

[

[ 10 ]

[

[

[

[

[

連結性（グラフ理論）

接続された頂点とグラフ

構成要素とカット

超接続性とハイパー接続性

メンガーの定理

計算上の側面

接続されたグラフの数

例

接続性の制限

その他の物件

関連項目

参考文献

関連するトピック

数学

コンピュータサイエンス

グラフ理論

独立したサブグラフに分割するために削除する必要のある要素（ノードまたはエッジ）の