K-辺連結グラフ

数学のグラフ理論において、あるグラフが"k"-辺連結（k-へんれんけつ、）であるとは辺連結度が"k"以上のグラフのことである。
言い換えると、グラフから "k" より少ない数の辺を除いてもであることを言う。
定義.
グラフ"G" = ("V","E") が与えられたとき、|"X"| < "k" であるような全ての "X" ⊆ "E" に対して "G"' = ("V","E" \ "X") が連結であるとき"G" は "k"-辺連結であると言う。明らかに、"G"が"k"-辺連結グラフならば"G"は ("k"−1)-辺連結である。
最小の頂点次数との関係.
最小の頂点次数は、辺連結度の自明な上界である。すなわち、グラフ "G" = ("E","V") が "k"-辺連結であるなら、必ず "k" ≤ δ("G") が成り立つ。但し、δ("G") は任意の頂点 "v" ∈ "V" の中での最小の次数を表す。明らかに、ある頂点 "v" に接続するすべての辺を取り除けば、"v" はそのグラフから離れて非連結となるであろう。
計算理論的側面.
辺連結度の算出.
辺連結度を決定するための多項式時間アルゴリズムが存在する。
ある簡単なアルゴリズムは、全てのペア "(u,v)" に対して、"G" 内のすべての辺の容量が両方向に対して 1 に定められているような、
"u" から "v" への最大フローを決定するものである。
グラフが "k"-辺連結であるための必要十分条件は、任意ペア "(u,v)" に対して "u" から "v" への最大フローは最小でも "k" であること、すなわち "k" が全ての "(u,v)" の中での最小の "u-v"-フローであることである。
"V" をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは formula_1 回の最大フロー問題の反復が行われ、時間 formula_2 内に解決される。したがって、この簡単なアルゴリズムの計算量は、総合すると formula_3 となる。
改善されたアルゴリズムでは、任意の固定された "u" と、固定されていない任意の "v" からなる全てのペア "(u,v)" に対する最大フロー問題を解く。このアルゴリズムでは計算量は formula_4 へと減らされており、適切なものである。なぜならば、もし容量が "k" より少ないカットが存在するのなら、それは "u" を他の頂点から切り離すからである。
k辺連結部分グラフの算出.
関連する問題: グラフ "G" の最小 "k"-辺連結部分グラフを見つける（すなわち、スケルトンが "k"-辺連結となるような可能な限り少ない辺をグラフから選択する）問題は、formula_5 に対してNP困難である。