第18章 二部图匹配算法（一）

简介：
本章介绍二部图的基本概念及其在实际问题中的应用，并详细讲解了二部图的最大匹配算法原理及求解方法。 二部图匹配算法是图论中的一个重要概念，在解决分配问题和网络流问题方面非常有用。一个二部图是由两个顶点集合X和Y组成的图形，其中每条边都连接了X集合中的一端与Y集合中的另一端，并且这两个集合之间没有交叉的边。 在处理二部图匹配时，我们的目标是找到最大匹配——即包含尽可能多无公共端点的边的子集。算法使用了一种改进后的增广路径方法来寻找这样的最大匹配。这种方法需要一个初始输入：一个当前的匹配M以及未被这个匹配覆盖的所有顶点集合U（也就是X中的那些没有通过任何一条属于M的边与Y中节点相连结的节点）。 该算法主要分为以下几个步骤： 1. 首先，将所有在集合U内的未饱和顶点标记为(*)且设定它们的状态为“未扫描”。 2. 如果上一步骤未能给X中的任一顶点赋予新的标记，则停止执行此过程。 3. 当存在一个被标记但尚未完成扫描的X集合内节点时（例如xi），就应当标识所有与它连接并且不属于M的所有边所对应的Y集合内的节点。同时，将xi的状态更新为“已扫描”。如果此时没有未被标记但是仍然需要检查的X集合顶点，则转至步骤4。 4. 如果在上一步骤中未能给任何新的Y集合内顶点赋予标识，则停止执行此过程；否则继续进行下一步操作。 5. 当有被标记但尚未完成处理工作的Y集合内的节点时（例如yi），则需要标注所有与之通过M中的边相连并且此前未曾标示过的X集合内的节点。接着，将yi的状态更新为“已扫描”。如果此时没有未被标记但是仍然需要检查的Y集合顶点，则返回步骤2。 算法中使用了两个关键概念：“突破”和“非突破”。 - 突破：指存在一个已被标识但尚未通过M中的边进行连接处理过的Y集合内的节点。这意味着我们可以找到一条新的增广路径，从而构建出比当前匹配多了一条边的新匹配。 - 非突破：表示每个被标记的Y顶点都已与某条属于M的边相连结了。这说明此时我们已经找到了一个最大可能大小的匹配。 根据匹配定理，反复应用该算法于二部图中将最终获得一个具有最优数量配对关系的最大匹配，并且可以构建出同样规模的最佳顶点覆盖集（即最小化未被完全连接的所有节点）。每次找到新的增广路径并更新当前最佳匹配时，都会减少至少一个尚未被覆盖的顶点。当算法无法再发现任何额外的有效连接路线后，此时得到的就是最大可能大小的最大匹配。 比如在一个给定的图G中应用这一过程来确定其最大匹配。假设初始输入为M1={(x2,y2), (x3,y3), (x4,y4)}（即当前最佳配对规模为3），未饱和顶点集合U={x1, x5, x6}，通过逐步扫描和标记操作可以找到该图的最大匹配并构造出相应的最小覆盖集。 这种算法在实际中非常有用，在网络路由、任务分配以及婚姻匹配等问题上都有广泛应用。掌握这一方法有助于有效解决许多现实世界中的优化问题。