連結性（グラフ理論）

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

無向グラフ Gにおいて、 2 つの頂点 uとv は、 G にuからvへのパスが含まれている場合、接続されていると呼ばれます。それ以外の場合、それらは非接続であると呼ばれます。2 つの頂点がさらに長さ1のパスによって接続されている(つまり、単一の辺の端点である) 場合、頂点は隣接していると呼ばれます。

グラフ内のすべての頂点のペアが接続されている場合は、そのグラフは接続されていると言われます。つまり、すべての頂点のペアの間にパスがあるということです。接続されていない無向グラフは、非接続と呼ばれます。したがって、無向グラフGに 2 つの頂点が存在し、その頂点をエンドポイントとするパスが G に存在しない場合は、そのグラフは非接続です。頂点が 1 つだけのグラフは接続されています。2つ以上の頂点を持つエッジのないグラフは非接続です。

有向グラフは、その有向辺をすべて無向辺に置き換えると連結（無向）グラフになる場合、弱連結と呼ばれます。すべての頂点 u 、 v に対して u から v への有向パス、または v から u への有向パスが含まれる場合、片側連結または片側（半連結とも呼ばれる）です。[2]すべての頂点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連結性は2 連結性とも呼ばれ、3連結性は3 連結性とも呼ばれます。連結されているが2連結ではないグラフG は、分離可能と呼ばれることもあります。

類似の概念をエッジについても定義できます。単一の特定のエッジをカットするとグラフが切断される単純なケースでは、そのエッジはブリッジと呼ばれます。より一般的には、 Gのエッジカットは、削除するとグラフが切断されるエッジの集合です。エッジ接続 λ ( G )は、最小のエッジカットのサイズであり、 2 つの頂点u、vのローカルエッジ接続λ ( u、v )は、 u をvから切断する最小のエッジカットのサイズです。この場合も、ローカルエッジ接続は対称です。グラフのエッジ接続がk以上の場合、そのグラフはkエッジ接続されていると呼ばれます。

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

グラフが超連結または超κグラフであるとは、すべての最小頂点カットが頂点を孤立させる場合である。グラフが超連結またはハイパーκグラフであるとは、すべての最小頂点カットを削除した結果、ちょうど2つの要素が作成され、そのうちの1つが孤立した頂点である場合である。グラフが半超連結または半ハイパーκグラフであるとは、任意の最小頂点カットがグラフをちょうど2つの要素に分割する場合である。^[4]

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

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

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

グラフの接続性に関する最も重要な事実の 1 つは、頂点間の独立したパスの数に基づいてグラフの接続性とエッジの接続性を特徴付ける メンガーの定理です。

uとv がグラフGの頂点である場合、 uとv間のパスのコレクションは、そのうちの 2 つが頂点を共有していない ( uとv自身以外) 場合、独立していると呼ばれます。同様に、コレクション内の 2 つのパスがエッジを共有していない場合、そのコレクションはエッジ独立です。uとv 間の相互に独立したパスの数はκ ′( u、v )と表され、uとv間の相互にエッジ独立なパスの数はλ ′( u、v )と表されます。

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

グラフ内の 2 つの頂点が接続されているかどうかを判断する問題は、幅優先探索などの検索アルゴリズムを使用して効率的に解決できます。より一般的には、グラフが接続されているかどうかを計算的に判断したり (たとえば、分離集合データ構造を使用して)、接続されているコンポーネントの数を数えたりすることは簡単です。単純なアルゴリズムは、次のように疑似コードで記述できます。

1. グラフGの任意のノードから開始します。
2. 深さ優先探索または幅優先探索のいずれかを使用してそのノードから進み、到達したすべてのノードをカウントします。
3. グラフが完全に走査された後、カウントされたノードの数がGのノードの数と等しい場合、グラフは接続されています。そうでない場合は、切断されています。

メンガーの定理により、連結グラフG内の任意の2 つの頂点uとvについて、最大フロー最小カットアルゴリズムを使用して、数κ ( u、v )とλ ( u、v )を効率的に決定できます。 Gの連結性と辺連結性は、それぞれκ ( u、v )とλ ( u、v )の最小値として計算できます。

計算複雑性理論において、SLは、グラフ内の2つの頂点が接続されているかどうかを判断する問題に対数空間で還元可能な問題のクラスであり、 2004年にオマー・ラインゴールドによってLに等しいことが証明されました。 ^[9]したがって、無向グラフの接続性はO(log n )空間で解決できます。

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

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

• 切断されたグラフの頂点と辺の接続性は両方とも0です。
• 1連結性は、少なくとも 2 つの頂点を持つグラフの連結性と同等です。
• n頂点の完全グラフの辺連結性はn − 1に等しくなります。n頂点の他のすべての単純グラフの辺連結性は厳密にこれより小さくなります。
• 木では、任意の 2 つの異なる頂点間のローカル エッジ接続は1です。

• グラフの頂点の接続性は、辺の接続性以下です。つまり、κ ( G ) ≤ λ ( G )です。
• 少なくとも2つの頂点を持つグラフの辺の接続性は、グラフの最小次数以下になります。これは、最小次数の頂点に接続するすべての辺を削除すると、その頂点がグラフの残りの部分から切断されるためです。^[1]
• 次数dの頂点推移グラフの場合、2( d + 1)/3≤κ ( G ) ≤λ ( G ) = dとなる。^[11]
• 次数d ≤ 4の頂点推移グラフ、または次数dの任意の（無向）極小ケイリーグラフ、または次数dの任意の対称グラフの場合、両方の種類の接続性は等しい：κ ( G ) = λ ( G ) = d。^[12]

• 連結性はグラフ準同型によって保存されます。
• Gが連結であれば、その線グラフ L ( G )も連結です。
• グラフG は、強く連結された方向を持つ場合にのみ、2辺連結です。
• バリンスキーの定理は、 k次元凸多面体の多面体グラフ（1-スケルトン）はk頂点連結グラフであることを述べています。^[13]任意の3頂点連結平面グラフは多面体グラフであるというスタインツの以前の定理（スタインツの定理）は、部分的な逆を与えます。
• GAディラックの定理によれば、グラフがk ≥ 2に対してk連結である場合、グラフ内のk頂点の集合ごとに、集合内のすべての頂点を通過する閉路が存在する。 ^{[14] [15]} k = 2のときは逆が成り立つ。

• 代数的接続性
• チーガー定数（グラフ理論）
• 動的接続性、分離集合データ構造
• エキスパンダーグラフ
• グラフの強さ