K-edge-connected graph

ウィキペディア

k-辺連結グラフ

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/01/24 09:59 UTC 版)

数学のグラフ理論において、あるグラフがk-辺連結（k-へんれんけつ、英: k-edge-connected）であるとは辺連結度が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 をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは $O(V^{2})$ 回の最大フロー問題の反復が行われ、時間 $O(V^{3})$ 内に解決される。したがって、この簡単なアルゴリズムの計算量は、総合すると $O(V^{5})$ となる。

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

k辺連結部分グラフの算出

関連する問題: グラフ G の最小 k-辺連結部分グラフを見つける（すなわち、スケルトンが k-辺連結となるような可能な限り少ない辺をグラフから選択する）問題は、$k\geq 2$ に対してNP困難である。

関連項目

数学的対象と性質

• k-頂点連結グラフ
• 連結グラフ
• カット (グラフ理論)
• 連結度

定理

• メンガーの定理
• ロビンスの定理

問題

• 辺連結度増大問題

Weblio日本語例文用例辞書

「K-edge-connected graph」の例文・使い方・用例・文例

• “Photo”は“Photograph”の略だ