メンガーの定理

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

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

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

メンガーの定理は、無限グラフでも成り立つことが証明されている。

 脚注 

 注釈 

 出典 

 参考文献 




 関連項目 
 カット (グラフ理論) (辺連結度について)
 連結グラフ

 外部リンク 


Category:グラフ理論の定理
Category:数学に関する記事