查找最小顶点给定匹配最大值的二分图覆盖

Question

我似乎找到了算法，但无法理解它，我想知道是否有人知道该算法的通用轮廓。

这里是链接到算法I 2页

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

Answer 1

上找到你首先应该知道二分图，两组顶点和边，OK，你现在知道了。

那么你需要从两组中选择一些顶点来覆盖所有的边。只要选择一个顶点，就会覆盖与其链接的所有边。现在你的任务是选择最小数量的顶点，以覆盖所有的边缘。

原理意味着，您需要的最小数量等于最大匹配对的数量。

Answer 2

算法是这么简单：

1. 查找匹配顶点，将其标记为不包括在最低顶点覆盖。
2. 将该顶点的所有匹配邻居标记为包含在最小顶点覆盖中。
3. 将上一步骤中所有顶点的配合视为不匹配的顶点并重复步骤1.
4. 如果递归结束，则从步骤1（即图的几个连接组件的情况）重复。
5. 如果没有不匹配的顶点，请取所有剩余的对并以任何喜欢的方式标记它们（请记住，对中的一个顶点必须包含在最小顶点覆盖中，而另一个顶点必须不包括 ）。

P.S.我知道这是necroposting。