最大基数匹配算法优化策略

依据文献[275]，下面给出最大基数匹配的相关概念。

定义2.1 （二分图），若图G=（V，E）的顶点集可划分为两个非空子集X和Y，使得G的任一条边都有一个端点在X中，另一个端点在Y中，则称G为二分图或二部图，记为G（X，Y）。

定义2.2 给定一个图G=（V，E）），设M是E的一个子集，如果M不含环且其中任意两边均不是邻接的，则称M是G的一个匹配。

定义2.3 如果某顶点和M的一条边关联，则称其为M-饱和点，否则称为M-非饱和点。如果G的每一点都是M-饱和点，则称M是G的完美匹配。

若M是G的边数最多的匹配，则称M是G的最大基数匹配。完美匹配是最大基数匹配。设M是G的一个匹配，G的一条M-交错路是指其边在M和E\M中交错出现的路。G的一条M-增广路是指起点和终点都是M-非饱和点的一条M-交错路。

定理2.3（Berge，1957） 图G中一个匹配M是最大基数匹配当且仅当G不包含M-增广路。

对于图G的任意一个顶点的子集X，定义X的邻域N（X）为与X中的点相邻接的所有点的全体。

定理2.4（Hall，1935） 设G为具有二划分（X，Y）的二分图，顶点集分划为S，T，则G有饱和S的每个顶点的匹配当且仅当对一切X⊆S，有|N（X）|≥|X|。

推论2.2（Frobenius，1917） 具备二划分（X，Y）的二分图G有完美匹配的充分必要条件是|X|=|Y|且对∀S⊆X（或Y），均有|N（S）|≥|S|。

定理2.5 设M是图G的匹配，C为G的覆盖，若|M|=|C|，则M是G的最大基数匹配，C是G的最小覆盖。

定理2.6 在二分图中，最大基数匹配的边数等于最小覆盖的顶点数。(www.xing528.com)

寻找增广路的标号法是由匈牙利人Egervary于1965年最早提出，因此称为匈牙利算法。算法基本思想为：任给匹配M出发（一开始可以是空集），若M饱和S的所有点，则M已经是最大基数匹配；否则，由S的M-非饱和点出发，用标号法寻找M-增广路直到找不M-增广路为止。

求解最大基数匹配的匈牙利算法如下：

Step1：在二分图中任取一个匹配M，所有顶点都没有标号。

Step2:

2.1若S中无M-非饱和点，则M为最大基数匹配，结束，否则对S中每个M-非饱和点标“0”和未检查，转2.2。

2.2如果S中所有标号的顶点都已检查，转Step4；否则取S中已标号未检查的顶点xi。

2.3若所有与xi相邻的顶点都已标号，则把xi改为已检查，转2.2；否则转2.4。

2.4把所有与xi相邻的未标号顶点yi都给予标号“i”，若其中某个yi是M-非饱和点，转Step3；否则对所有yi，把与yi在M中配对的顶点yi给予标号“j”和未检查，并把xp改为已检查，转2.2。

Step3：从得到标号T中的M-非饱和点yj开始反向搜索，一直找到S中标号为“0”的M-非饱和点xi为止，得到G中M-增广路P，M=M⊕P=（M∪P）/（M∩P），去掉M中所有顶点标号，转Step2。

Step4：M是G的最大基数匹配，结束。