图2-4
增广路径：1 -> 2->3->4->5->6。1、6非匹配点，中间结点2、3、4、5是匹配点。黑色标记 1--->2、3--->4、5--->6是非匹配边，红色标记2-3、4-5是匹配边。
增广路径的首尾是非匹配点。因此，增广路径的第一条和最后一条边，必然是非匹配边；同时它的第二条边（如果有）和倒数第二条边（如果有），必然是匹配边；以及第三条边（如果有）和倒数第三条边（如果有），一定是非匹配边。
增广路径从非匹配边开始，匹配边和非匹配边依次交替，最后由非匹配边结束。这样一来，增广路径中非匹配边的数目会比匹配边大 1。
如果我们置换增广路径中的匹配边和非匹配边，由于增广路径的首尾是非匹配点，其余则是匹配点，这样的置换不会影响原匹配中的匹配点，匹配中不包含在该路径中的其他匹配边也不受到影响，因而不会破坏匹配；增广路径的置换，可以得到比原有匹配更大的匹配（具体来说，匹配的边数增加了 1）。
增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，匹配边数目比原来多了 1 条。
由于二分图的最大匹配必然存在（比如，上限是包含所有顶点的完全匹配），所以，在任意匹配的基础上，如果我们有办法不断地搜寻出增广路径，直到最终我们找不到新的增广路径为止，我们就有可能得到二分图的一个最大匹配。这就是匈牙利算法的核心思想。
唯一的问题在于，在这种贪心的思路下，我们如何保证不存在例外的情况，即：当前匹配不是二分图的最大匹配，但已找不到一条新的增广路径。
我们从反证法考虑，即假设存在这样的情况。因为当前匹配不是二分图的最大匹配，那么在两个集合中，分别至少存在一个非匹配点。那么情况分为两种：
1)、这两个点之间存在一条边——那么我们找到了一条新的增广路径，产生矛盾；
2)、这两个点之间不存在直接的边，即这两个点分别都只与匹配点相连——那么：
a、如果这两个点可以用已有的匹配点相连，那么我们找到了一条新的增广路径，产生矛盾；
b、如果这两个点无法用已有的匹配点相连，那么这两个点也就无法增加匹配中边的数量，也就是我们已经找到了二分图的最大匹配，产生矛盾。
在所有可能的情况，上述假设都会产生矛盾。因此假设不成立，亦即贪心算法必然能求得最大匹配的解。
由增广路径的定义可以推出的三个结论：
①P的路径长度必定为奇数，第一条边和最后一条边都不属于M；
②P经过置换(取反)操作可以得到一个更大的匹配M；
③M为G的最大匹配当且仅当不存在相对于M的增广路径。
增广路的应用- 增广路用于证明最大匹配问题。
- 增广路主要应用于匈牙利算法中，用于求二分图最大匹配。
匈牙利树一般由 BFS 构造（类似于 BFS 树）。从一个未匹配点出发运行 BFS（唯一的限制是，必须走交替路），直到不能再扩展为止。如图2-5，由Fig.7，可以得到Fig.8的一棵 BFS 树。
图2-5
这棵树存在一个叶子结点为非匹配点（7号），但是匈牙利树要求所有叶子结点均为匹配点，因此这不是一棵匈牙利树（顺便说一句，Fig.8 中非匹配根节点2到非匹配叶结点7显然是一条增广路，沿这条增广路扩充后将得到一个完美匹配）。在Fig.9中，从2号结点出发就会得到一棵匈牙利树。
匈牙利树要求所有叶子结点均为匹配点，它就是把存在的可连接的匹配点都列出来。
4、二分图最大匹配数=最小点覆盖率二分图的最小点覆盖的理解：找到最少的一些点，使二分图所有的边都至少有一个端点在这些点之中。倒过来说就是，删除包含这些点的边，可以删掉所有边。
三、匈牙利算法复杂度设V为二分图左边的顶点数，E为二分图中边的数目。匈牙利算法的实现以与点集合 V 为基础，每次在集合V中选一个顶点 Vi 做增广路径的起点搜索增广路径。搜索增广路径需要遍历边及E内的所有边，遍历方法可以采用深度优先遍历（DFS），也可以采用广度优先遍历（BFS），无论什么方法，其时间复杂度都是 O(E)。
匈牙利算法每个顶点 Vi 只能选择一次，因此算法的整体时间复杂度是 O(V*E)，总的来说，是一个相当高效的算法。
假设在婚介公司的手上有4位剩男，4位剩女，还没见面只是互相看了资料，每个人都对多名异性有好感。婚介公司做了一张互有好感关系图。如图4-1所示。
图4-1
是否可能让所有男孩和女孩一对一配对，使得每对儿都互相喜欢呢？在图论中，这就是完美匹配问题。如果换一个说法：最多有多少互相喜欢的男孩/女孩可以配对儿？这就是最大匹配问题。匈牙利算法就是为了求解最大匹配问题。
解法一第1步 初始为空匹配。如图4-2所示。
图4-2
第2步 选择空匹配点Al、Alice，建立第1条增广路径Al--->Alice, 并进行置换，创建第1个匹配：红色标记Al--->Alice。如图4-3所示。
