二分图匹配相关

发布网友发布时间：2024-10-16 01:15

共1个回答

热心网友时间：2024-10-16 20:55

二分图是图的一种，节点由两个集合组成，同一集合内两点之间无边，任意边的两点必须属于不同集合。例如Fig.1不是二分图，Fig.2、Fig.3、Fig.4则是。匹配是边的集合，集合内任意两条边无公共顶点。Fig.3和Fig.4展示了Fig.2的不同匹配。匹配点是匹配中包含的点，未匹配点是匹配中未包含的点；匹配边是匹配中的边，非匹配边是匹配中的边。最大匹配是针对某图，包含匹配边最多的匹配。Fig.4中的匹配即为其最大匹配，包含4条匹配边。完美匹配是指某匹配使得图中的所有顶点均为匹配点。显然，完美匹配一定是最大匹配，但并非每个图都存在完美匹配。

匈牙利算法适用于求解任意二分图的最大匹配问题，无需二分图存在完美匹配，最大匹配也不一定完美匹配。主要思路是不断寻找交替路和增广路，进行翻转操作，确保每次翻转操作增加且仅增加一条匹配边。交替路是从未匹配点出发，依次经过非匹配边、匹配边、非匹配边的路径。增广路是从未匹配点出发的交替路，终点为未匹配点。翻转是将增广路中的匹配边和非匹配边分别转换为非匹配边和匹配边。增广路的重要特性之一是，当所有左集合节点都不存在增广路径时，所有右集合节点也不会存在增广路径。通过反证法证明了这一命题，只需遍历左集合的未匹配点而无需遍历右集合的未匹配点。匈牙利算法最终得到的最大匹配是针对给定图的最优匹配。