为防止广告，目前nocow只有登录用户能够创建新页面。如要创建页面请先登录/注册（新用户需要等待1个小时才能正常使用该功能）。
Edmonds' Blossom-Contraction
来自NOCOW
这是一个利用增广路求一般图最大匹配的算法，由匈牙利数学家Edmonds于1965年提出，又名匈牙利算法。
求最大匹配的一种显而易见的算法是：先找出全部匹配，然后保留匹配数最多的。但是这个算法的复杂度为边数的指数级函数。因此，需要寻求一种更加高效的算法。
[编辑] 增广路
增广路的定义(也称增广轨或交错轨)：
若P是图G中一条连通两个未匹配顶点的路径，并且属M的边和不属M的边(即已匹配和待匹配的边)在P上交替出现，则称P为相对于M的一条增广路径。
由增广路的定义可以推出下述三个结论：
- P的路径长度必定为奇数，第一条边和最后一条边都不属于M。
- P经过取反操作可以得到一个更大的匹配M’。
- M为G的最大匹配当且仅当不存在相对于M的增广路径。
[编辑] 算法轮廓
- 置M为空
- 找出一条增广路径P，通过取反操作获得更大的匹配M’代替M
- 重复(2)操作直到找不出增广路径为止
