1. 二分图概念

　　二分图又称作二部图，是图论中的一种特殊模型。 设G=(V,E)是一个无向图，如果顶点V可分割为两个互不相交的子集(A,B)，并且图中的每条边（i，j）所关联的两个顶点i和j分别属于这两个不同的顶点集(i in A,j in B)，则称图G为一个二分图。

2.匹配

　　在图论中，一个「匹配」（matching）是一个边的集合，其中任意两条边都没有公共顶点。最大匹配就是一个图所有匹配中，所含匹配边数最多的匹配，称为这个图的最大匹配；完美匹配：如果一个图的某个匹配中，所有的顶点都是匹配点，那么它就是一个完美匹配。

3.匈牙利算法

3.1 涉及的一些基本概念

3.1.1 交替路

　　从一个未匹配点出发，依次经过非匹配边、匹配边、非匹配边...形成的路径叫交替路。

3.1.2 增广路

　　从一个未匹配点出发，走交替路，如果途径另一个未匹配点（出发的点不算），则这条交替路称为增广路（agumenting path）。例如，图 5 中的一条增广路如图 6 所示（图中的匹配点均用红色标出）。

        

　　增广路有一个重要特点：非匹配边比匹配边多一条。因此，研究增广路的意义是改进匹配。只要把增广路中的匹配边和非匹配边的身份交换即可。由于中间的匹配节点不存在其他相连的匹配边，所以这样做不会破坏匹配的性质。交换后，图中的匹配边数目比原来多了 1 条。

我们可以通过不停地找增广路来增加匹配中的匹配边和匹配点。找不到增广路时，达到最大匹配（这是增广路定理）。匈牙利算法正是这么做的。