|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ ー ： [ちょうおん] (n) long vowel mark (usually only used in katakana) ・ 定理 ： [ていり] 【名詞】 1. theorem 2. proposition ・ 理 ： [り] 【名詞】 1. reason
メンガーの定理（英: Menger's theorem）とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。 辺連結度版のメンガーの定理は次の通りである。有限無向グラフ ''G'' で、''x'' と ''y'' が隣接していない頂点であるとする。このとき、''x'' と ''y'' の最小辺カット（辺切断。除去することで ''x'' と ''y'' が連結されなくなる最小の辺の数）の大きさは、''x'' から ''y'' の辺独立経路 (辺素パス) の最大数と等しい。 点連結度版のメンガーの定理は次の通りである。有限無向グラフ ''G'' で、''x'' と ''y'' が隣接していない頂点であるとする。このとき、''x'' と ''y'' の最小点カット（点切断。除去することで ''x'' と ''y'' が連結されなくなる最小の頂点の数）の大きさは、''x'' から ''y'' の頂点独立経路 (点素パス) の最大数と等しい。 メンガーの定理は、無限グラフでも成り立つことが証明されている（ポール・エルデシュが最初に推測していた）。 == 関連項目 == * カット (グラフ理論) (辺連結度について) * 連結グラフ 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「メンガーの定理」の詳細全文を読む スポンサード リンク
|