k-辺連結グラフとは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > 百科事典 > k-辺連結グラフの意味・解説 

k-辺連結グラフ

出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2025/08/18 01:13 UTC 版)

数学グラフ理論において、あるグラフがk-辺連結(k-へんれんけつ、: k-edge-connected)であるとは辺連結度k以上のグラフのことである。 言い換えると、グラフから k より少ない数の辺を除いても連結英語版であることを言う。

定義

グラフG = (V,E) が与えられたとき、|X| < k であるような全ての X ⊆ E に対して G' = (V,E \ X) が連結であるときGk-辺連結であると言う。明らかに、Gk-辺連結グラフならば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 をグラフに含まれる頂点の数としたとき、この簡単なアルゴリズムでは カテゴリ / コモンズ



このページでは「ウィキペディア」からk-辺連結グラフを検索した結果を表示しています。
Weblioに収録されているすべての辞書からk-辺連結グラフを検索する場合は、下記のリンクをクリックしてください。
 全ての辞書からk-辺連結グラフ を検索

英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「k-辺連結グラフ」の関連用語

k-辺連結グラフのお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



k-辺連結グラフのページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
All text is available under the terms of the GNU Free Documentation License.
この記事は、ウィキペディアのk-辺連結グラフ (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。 Weblio辞書に掲載されているウィキペディアの記事も、全てGNU Free Documentation Licenseの元に提供されております。

©2025 GRAS Group, Inc.RSS