K-辺連結グラフのソースを表示

{{DISPLAYTITLE:''k''-辺連結グラフ}}
[[数学]]の[[グラフ理論]]において、あるグラフが'''''k''-辺連結'''（k-へんれんけつ、{{Lang-en-short|''k''-edge-connected}}）であるとは[[連結グラフ|辺連結度]]が''k''以上のグラフのことである。
言い換えると、グラフから ''k'' より少ない数の辺を除いても{{仮リンク|連結度|label=連結|en|connectivity (graph theory)}}であることを言う。

== 定義 ==
グラフ''G''&nbsp;=&nbsp;(''V'',''E'') が与えられたとき、|''X''|&nbsp;<&nbsp;''k'' であるような全ての ''X''&nbsp;⊆&nbsp;''E'' に対して ''G'''&nbsp;=&nbsp;(''V'',''E''&nbsp;\&nbsp;''X'') が連結であるとき''G'' は ''k''-辺連結であると言う。明らかに、''G''が''k''-辺連結グラフならば''G''は (''k''&minus;1)-辺連結である。

== 最小の頂点次数との関係 ==
最小の[[次数 (グラフ理論)|頂点次数]]は、辺連結度の自明な上界である。すなわち、グラフ ''G''&nbsp;=&nbsp;(''E'',''V'') が ''k''-辺連結であるなら、必ず ''k''&nbsp;≤&nbsp;δ(''G'') が成り立つ。但し、δ(''G'') は任意の頂点 ''v''&nbsp;∈&nbsp;''V'' の中での最小の次数を表す。明らかに、ある頂点 ''v'' に接続するすべての辺を取り除けば、''v'' はそのグラフから離れて非連結となるであろう。

== 計算理論的側面 ==
=== 辺連結度の算出 ===
[[連結グラフ|辺連結度]]を決定するための[[多項式時間アルゴリズム]]が存在する。
ある簡単なアルゴリズムは、全てのペア ''(u,v)'' に対して、''G'' 内のすべての辺の容量が両方向に対して 1 に定められているような、
''u'' から ''v'' への[[最大フロー問題|最大フロー]]を決定するものである。
グラフが ''k''-辺連結であるための必要十分条件は、任意ペア ''(u,v)'' に対して ''u'' から ''v'' への最大フローは最小でも ''k'' であること、すなわち ''k'' が全ての ''(u,v)'' の中での最小の ''u-v''-フローであることである。

''V'' をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは <math>O(V^2)</math> 回の最大フロー問題の反復が行われ、時間 <math>O(V^3)</math> 内に解決される。したがって、この簡単なアルゴリズムの計算量は、総合すると <math>O(V^5)</math> となる。

改善されたアルゴリズムでは、任意の固定された ''u'' と、固定されていない任意の ''v'' からなる全てのペア ''(u,v)'' に対する最大フロー問題を解く。このアルゴリズムでは計算量は <math>O(V^4)</math> へと減らされており、適切なものである。なぜならば、もし容量が ''k'' より少ない[[カット (グラフ理論)|カット]]が存在するのなら、それは ''u'' を他の頂点から切り離すからである。

===k辺連結部分グラフの算出===
関連する問題: グラフ ''G'' の最小 ''k''-辺連結部分グラフを見つける（すなわち、スケルトンが ''k''-辺連結となるような可能な限り少ない辺をグラフから選択する）問題は、<math>k\geq 2</math> に対して[[NP困難]]である<ref>M.R. Garey and D.S. Johnson. ''Computers and Intractability: a Guide to the Theory of NP-Completeness''. Freeman, San Francisco, CA, 1979.</ref>。

== 参考文献 ==
{{reflist}}

== 関連項目 ==
=== 数学的対象と性質 ===
* [[k-頂点連結グラフ]]
* [[連結グラフ]]
* [[カット (グラフ理論)]]
* {{仮リンク|連結度|en|Connectivity (graph theory)}}
=== 定理 ===
* [[メンガーの定理]]
* {{仮リンク|ロビンスの定理|en|Robbins theorem}}
=== 問題 ===
* [[辺連結度増大問題]]

{{DEFAULTSORT:けいへんれんけつくらふ}}
[[Category:グラフ理論のグラフ|Kへんれんけつくらふ]]
[[Category:数学に関する記事]]