K-辺連結グラフ

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

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

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

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

数学的対象と性質

• k-頂点連結グラフ
• 連結グラフ
• カット (グラフ理論)
• 連結度（英語版）

定理

• メンガーの定理
• ロビンスの定理（英語版）

問題

• 辺連結度増大問題

表 話 編 歴 グラフ理論
要素・定義・表現	頂点 辺（英語版） グラフ 無向 有向 ラベル付き（英語版） 重み付き（英語版） ハイパーグラフ 接続行列 隣接行列 隣接リスト ラプラシアン行列
指標	位数（英語版） サイズ（英語版） 次数 次数行列 距離（英語版） 半径 直径 内周 (頂点)彩色数 辺彩色数（英語版） 点連結度 辺連結度 交叉数（英語版）
部分構造	ループ（英語版） 多重辺（英語版） 部分グラフ（英語版） 誘導部分グラフ 道 閉道 連結成分（英語版） 強連結成分（英語版） 橋（英語版） カット クリーク 独立集合 支配集合 マッチング オイラー路 シュタイナー木 全域木 ハミルトン路
全体構造	連結グラフ 正則グラフ 立方体グラフ ケージ 強正則グラフ 木 平面グラフ 2部グラフ 有向非巡回グラフ 弦グラフ ムーアグラフ パーフェクトグラフ 対称グラフ 半対称グラフ 頂点推移グラフ 辺推移グラフ 距離推移グラフ 補グラフ 双対グラフ グラフ同型
固有名を持つグラフ	パスグラフ（英語版）Pn 閉路グラフCn 完全グラフKn 完全2部グラフKm,n スターSn = K1,n 車輪グラフWn 空グラフ ピーターセングラフ ヒーウッドグラフ マギーグラフ ホフマンシングルトングラフ フォークマングラフ
トピック・定理	一筆書き オイラーの多面体定理 クラトフスキの定理 四色定理 五色定理 ケイリーの公式 プリューファー列 最短経路問題 巡回セールスマン問題 中国人郵便配達問題 ダイクストラ法 ベルマン-フォード法 ワーシャル-フロイド法 ハミルトン閉路問題 最大クリーク問題 頂点被覆問題 最小頂点被覆問題 最大独立集合問題 最大流最小カット定理 最大カット問題 支配集合問題 次数直径問題 安定結婚問題
カテゴリ / コモンズ