门杰定理

门杰定理(Menger's theorem)又称“Menger定理”，是关于图的连通性的一个定理，门杰定理断言：若X和Y是图G的两个不交的节点子集，k是一个正整数，则G上存在k条分别以X和Y中的节点为端点而且两两除端点外互不交的路，当且仅当每一个XY分离点集包含至少k个节点，上述的XY分离点集指G的这样一个节点子集，若从G上去掉该子集的所有节点，所得到的图不存在连X中节点与Y中节点的路，这个定理是门杰(K.Menger)于1927年首先发现的，于是，由此而得名。1927年，Menger证明了图的连通性与图中连接两个顶点的不相交路的数目有关。Menger定理非常有用，由它产生了许多关于图的连通性的很多变种结论，而且它与Hall匹配定理与最大流量最小割定理以及其他一些离散数学中的重要结论都密切相关。