定义

基本定义

给定一个二分图G，M为G边集的一个子集，如果M满足当中的任意两条边都不依附于同一个顶点，则称M是一个匹配。

极大匹配(Maximal Matching)是指在当前已完成的匹配下,无法再通过增加未完成匹配的边的方式来增加匹配的边数。最大匹配(maximum matching)是所有极大匹配当中边数最大的一个匹配。选择这样的边数最大的子集称为图的最大匹配问题。

如果一个匹配中，图中的每个顶点都和图中某条边相关联，则称此匹配为完全匹配，也称作完备匹配。

求二分图最大匹配可以用最大流(Maximal Flow)或者匈牙利算法(Hungarian Algorithm)

图

设G=(V，E)是一个图，M是E的一个子集，如果M不含环且任意两边都不相邻，则称M为G的一个匹配。G中边数最多的匹配称为G的最大匹配。　对于图G=(V，E)，在每条边e上赋一个实数权w(e)。设M是G的一个匹配。定义 ，并称之为匹配M的权。G中权最大的匹配称为G的最大权匹配。如果对一切，e∈E，w(e)=1,则G的最大权匹配就是G的最大匹配。

匹配

设M是图G=(V,E)的一个匹配，vi∈V。若vi与M中的边相关联，则称vi是M饱和点，否则称vi为M非饱和点。　如果G中每个顶点都是M饱和点，则称M为G的完美匹配。　设M是G的一个匹配，P是G的一条链。如果P的边交替地一条是M中的边，一条不是M中的边，则称P为M交错链。类似地，我们可以定义G的交错圈。易知，G的交错圈一定是偶圈。　一条连接两个不同的M非饱和点的M交错链称为M增广链。　两个集合S1与S2的“异或”操作S1⊕S2是指集合S1⊕S2=（S1∩S2）\\（S1∪S2）　容易看出，设M是G的匹配，P是G中的M增广链、则M⊕P也是G的匹配，而且　可以证明，G中匹配M是最大匹配当且仅当G中没有M增广链。