打开主菜单

图论中,门格尔定理(英:Menger's Theorem)指在有限图中,最小割集英语cut set的大小等于任意在所有顶点对之间可以找到的不相交路径的最大数量。这一定理的证明由卡尔·门格尔于1927年发表。这被认为是图论中最重要且经典的定理之一。该定理刻畫了连通性的性质,增加了邊的權重可推廣成最大流量小割定理,而最大流量小割定理是線性規劃的强对偶性定理的直接推論。

目录

参见编辑

参考文献编辑


延伸阅读编辑

外部链接编辑