エッジ接続

グラフ理論において、連結グラフは、 k個未満の辺を削除しても連結状態が維持される場合、k辺連結であると言われる。

グラフのエッジ連結性とは、グラフがkエッジ連結となる最大のkの値のことである。

エッジ連結性とkエッジ連結グラフの列挙は、 1869年にカミーユ・ジョルダンによって研究された。 ^{[ 1 ]}

させて${\displaystyle G=(V,E)}$任意のグラフとする。部分グラフが${\displaystyle G'=(V,E\setminus X)}$すべての人がつながっています${\displaystyle X\subseteq E}$どこ${\displaystyle |X|<k}$の場合、Gはkエッジ連結であると言われる。${\displaystyle G}$は、 Gがkエッジ連結となるような最大値kである。Gを分断する最小の集合X は、 Gにおける最小カットである。

メンガーの定理の辺連結性バージョンは、グラフ内の辺素なパスという観点から、代替的かつ同等の特徴付けを提供する。グラフGの任意の 2 つの頂点がk個のパスの端点を形成し、それらのパスの 2 つが互いに辺を共有しない場合に限り、Gはk辺連結である。一方向ではこれは簡単である。このようなパスのシステムが存在する場合、k個未満の辺からなる任意の集合Xは、少なくとも 1 つのパスと互いに素であり、 Xを削除した後でも頂点のペアは互いに連結されたままである。もう一方の方向では、少数の辺を削除しても切断されないグラフ内の任意の頂点のペアに対するパスのシステムの存在は、ネットワーク フローの理論からの最大フロー最小カット定理を使用して証明できる。

最小頂点次数は、辺連結性の自明な上限を与える。つまり、グラフが${\displaystyle G=(V,E)}$がkエッジ連結である場合、 k  ≤  δ( G )である必要がある。ここで、δ( G ) は任意の頂点v  ∈ Vの最小次数である。頂点vに接続するすべてのエッジを削除すると、 vはグラフから切り離される。 

エッジ接続性は、グラフの最短サイクルの長さである周長と双対概念であり、平面グラフの周長はその双対グラフのエッジ接続性であり、その逆もまた然りです。これらの概念は、マトロイド理論において、マトロイドの周長、すなわちマトロイド内の最小依存集合のサイズによって統一されます。グラフィックマトロイドの場合、マトロイドの周長は基となるグラフの周長に等しく、コグラフィックマトロイドの場合はエッジ接続性に等しくなります。^{[ 2 ]}

2辺連結グラフは、ブリッジの不在、耳分解の存在、またはロビンスの定理（これこそが強い向き付けを持つグラフである）によって特徴づけられる。^{[ 3 ]}

ナッシュ・ウィリアムズの定理の系により、グラフのエッジ連結性は、グラフ内にいくつのエッジ素な全域木が存在するかについての上限を与える。

グラフGがkエッジ連結となる最大のkを決定する多項式時間アルゴリズムが存在する。単純なアルゴリズムでは、任意のペア(u,v)に対して、Gのすべてのエッジの容量を両方向とも 1 に設定して、 uからvへの最大フローを決定する。グラフがkエッジ連結となるのは、任意のペア(u,v)に対してuからvへの最大フローが少なくともkである場合のみであり、したがってk はすべての(u,v)の中で最小のuvフローである。

nがグラフの頂点の数である場合、この単純なアルゴリズムは${\displaystyle O(n^{2})}$最大フロー問題の反復は、${\displaystyle O(n^{3})}$時間。したがって、上述の単純なアルゴリズムの複雑さは${\displaystyle O(n^{5})}$合計で。

改良されたアルゴリズムは、 uが任意に固定され、v がすべての頂点で変化するすべてのペア(u,v)に対して最大フロー問題を解決します。これにより複雑さが軽減され、${\displaystyle O(n^{4})}$また、容量がk未満のカットが存在する場合、それは必ずu を他の頂点から分離するため、健全である。さらに、最悪の場合に実行されるGabowのアルゴリズムによって改善することができる。${\displaystyle O(n^{3})}$時間。^{[ 4 ]}

KargerアルゴリズムのKarger–Stein変種は、接続性を決定するためのより高速なランダム化アルゴリズムを提供し、期待実行時間は${\displaystyle O(n^{2}\log ^{3}n)}$[ ^{5 ]​}

関連する問題： Gの最小kエッジ連結全域部分グラフを見つけること（つまり、選択したエッジがkエッジ連結であるG内のエッジをできるだけ少なく選択すること）は NP 困難である。${\displaystyle k\geq 2}$[ ^{6 ]​}

• k個の頂点が連結したグラフ
• 連結性（グラフ理論）
• 一致排除