k辺連結グラフ

グラフ理論では、k辺未満の辺が削除されても接続されたままになる連結グラフは、k辺連結であるといいます。

グラフの辺接続性は、グラフがk辺接続されている最大のkです。

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

を任意のグラフとします。のすべての場合にサブグラフが連結されている場合、G はk辺連結であるといいます。 の辺連結性は、 Gがk辺連結となるようなk の最大値です。削除するとGが切断される最小の集合X は、 Gにおける最小カットです。 ${\displaystyle G=(V,E)}$ ${\displaystyle G'=(V,E\setminus X)}$${\displaystyle X\subseteq E}$${\displaystyle |X|<k}$${\displaystyle G}$

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

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

辺の連結性は、グラフの最短サイクルの長さである内周と双対の概念であり、平面グラフの内周はその双対グラフの辺の連結性であり、逆もまた同様である。これらの概念は、マトロイド理論において、マトロイドの内周、つまりマトロイド内の最小の従属集合のサイズによって統一される。グラフィックマトロイドの場合、マトロイドの内周は基になるグラフの内周に等しく、コグラフィックマトロイドの場合は辺の連結性と等しい。^[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)の最大フロー問題を解きます。これにより、複雑さが に軽減され、容量がk未満のカットが存在する場合、 u を他の頂点から分離する必要があるため、健全です。これは、最悪の場合の時間で実行されるGabowのアルゴリズムによってさらに改善できます。 ^[4]${\displaystyle O(n^{4})}$${\displaystyle O(n^{3})}$

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

関連する問題: Gの最小のk辺連結な全域部分グラフを見つけること(つまり、 G内でk辺連結となる辺をできるだけ少なく選択すること)はNP困難である。^[6]${\displaystyle k\geq 2}$

• k 頂点連結グラフ
• 連結性（グラフ理論）
• マッチングの排除