algorithm - 给定最大匹配找到二分图的最小顶点覆盖

Question

我似乎找到了一种算法，但我很难理解它，我想知道你们中是否有人知道该算法的通用概要。

这是我在第 2 页找到的算法的链接

http://www.cse.iitb.ac.in/~sundar/cs435/lecture23.pdf

Answer 1

算法就这么简单:

1. 找到不匹配的顶点，将其标记为不包含在最小顶点覆盖中。
2. 将此顶点的所有匹配邻居标记为包含在最小顶点覆盖中。
3. 将上一步中的所有顶点配对视为不匹配的顶点并重复步骤 1。
4. 如果递归结束，则从步骤 1 开始重复(即图的多个连通分量的情况)。
5. 如果没有不匹配的顶点，取出所有剩余的对并以任何你喜欢的方式标记它们(记住一对中的一个顶点必须包含在最小顶点覆盖中，另一个必须不包括)。