メンガーの定理

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動: 案内検索

メンガーの定理: Menger's theorem)とは、グラフ理論および関連する数学の分野における定理であり、有限無向グラフに属する連結グラフに関する定理である。カール・メンガーが1927年、辺連結度と点連結度について見出した。辺連結度版のメンガーの定理は、後に最大フロー最小カット定理として一般化された。

辺連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、xy が隣接していない頂点であるとする。このとき、xy の最小辺カット(辺切断。除去することで xy が連結されなくなる最小の辺の数)の大きさは、x から y辺独立経路 (辺素パス) の最大数と等しい。

点連結度版のメンガーの定理は次の通りである。有限無向グラフ G で、xy が隣接していない頂点であるとする。このとき、xy の最小点カット(点切断。除去することで xy が連結されなくなる最小の頂点の数)の大きさは、x から y頂点独立経路 (点素パス) の最大数と等しい。

メンガーの定理は、無限グラフでも成り立つことが証明されている(ポール・エルデシュが最初に推測していた)。

関連項目[編集]

参考文献[編集]

外部リンク[編集]