定义：若，与无公共端点（）则称为图中的一个对集；中的一条边的两个端点叫做在对集中相匹配;中的端点称为被M许配；中每个顶点皆被许配时，称为完美对集；若中已没有的对集，则称为最大对集；若中有一轨，其边交替地在对集内外出现，则称此轨为的交错轨，此交错轨的起止顶点都未被许配时，此交错轨成为増广轨。

示意图

如上图所示，红线所标的三条边即是一个对集，由于只剩一个顶点没在这个对集的顶点中，所以不可能找到起止顶点都未能许配的増广轨，所以这个对集是它的最大对集，但是不是完美对集。

1957年，贝尔热(Berge)得到最大对集的充要条件：

定理1 是图的最大对集当且仅当中无可増广轨。

定理2 为二分图，和是顶点集的划分，中存在把中的顶点都许配的对集的充要条件是：，则其中是的邻集。

由以上定理可推得：

推论1 若是次（）正则2分图，则有完美对集。
（次正则图：每顶点都有度的图）

由以上定理，可得婚配定理：

定理3 每个姑娘都结识个小伙子，每个小伙子都结识个小姑娘，那么每个小伙子都能找到一个小姑娘结婚，每个小姑娘都能找到一个小伙子结婚。

下面提出一个利用对集概念解决的问题：人员分派问题：

例1 工作人员去做件工作，每人适合做其中的一件或几件，问是否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？

解决这个问题可以用1965年爱得门兹(Edmonds)提出的匈牙利算法。

匈牙利算法

1.从中任意取定一个初始对集。
2.若把中的顶点皆许配，停止，即是完美对集；否则取中未被许配的一顶点，记
3.若，停止，无完美对集；否则取
4.若是被许配的，设，转回3继续。否则，取可増广轨，令，转回2。

最优分派问题

在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。

这个问题的数学模型是：在人员分派问题的模型中，图的每边加了权，表示干工作的效益，求加权图上的权最大完美对集。

解决这个问题可以用库恩—曼克莱斯（Kuhn-Munkres）算法。为此，我们要引入可行顶点标号与相等子图的概念。

定义：若映射，满足，

则称是二分图的可行顶点标号。令：

称为以为边集的的生成子图为相等子图，记做。

可行顶点标号举例：

必然是一组可行顶点标号。

定理4 的完美对集即是的权最大完美对集。

kuhn-Munkres算法

1.选定初始可行顶点标号，确定，在中选取一个对集
2.若中顶点皆被许配，停止，即为的权最大的完美对集，否则，取中未被许配的顶点，令
3.若，转4，若，取


4.选中选一顶点，若已被许配，且，则，转3，否则，取中可増广轨，令
转2
其中是中的相邻顶点集。