交错轨

交错轨定义如概述图所示。摘至王树禾的离散数学引论。由交错轨的定义可以推出下述三个结论：　1－P的路径长度必定为奇数，第一条边和最后一条边都不属于M。　2－不断寻找增广路可以得到一个更大的匹配M’，直到找不到更多的交错轨。　3－M为G的最大匹配当且仅当不存在M的交错轨。