algorithm - 二分图上的最小顶点覆盖

Question

假设您有一个二分图 G = (V, U, E)

v1 连接到 u1、u2 和 u3

v2 连接到 u2 和 u3

v3 连接到 u3。

通过查看图表，我知道最小顶点覆盖是{v1，v2，u3}和{v1，u2，u3}，但我不确定如何使用二分匹配/顶点覆盖算法来找出这个. 这里 和这里

当我手动执行算法时，输出只是微不足道的最小顶点覆盖，所有 V。我做错了什么吗？

编辑：

图的最大匹配是边 (v1, u1)、(v2, u2) 和 (v3, u3)。给定最大匹配，下一步是从不饱和顶点（不是匹配边的端点之一的顶点）开始

但在这种情况下，所有顶点都已饱和，所以我不知道如何进行。

Answer 1

Konig 定理有两个方向。与弱线性规划对偶相对应的简单方向是顶点覆盖至少与匹配一样大。这是因为，在每个顶点覆盖中，每个匹配边都至少存在一个端点。

Konig 定理的硬方向，对应于强 LP 对偶性，是存在一个顶点覆盖，其中每个匹配边的最多（即恰好）一个端点存在。维基百科当前证明的主旨是使用匹配来贪婪地构造一个顶点覆盖，表明如果这个算法卡住了，那么所谓的最大匹配有一条​​增广路径（矛盾）。每条边都与匹配的顶点相关，因此可以从覆盖中排除不匹配的顶点。反过来，他们的邻居也必须包括在内。他们的邻居的邻居可以被排除在外，等等。

您已经注意到，此过程有时无法确定每个顶点的状态。对于这种情况，维基百科的编辑写道：“如果没有这样的顶点，但仍有未包含在任何先前定义的集合 Sk 中的顶点，则任意选择其中一个，让 S2j+1 由该单个顶点组成。” 证明此步骤合理性的一种方法如下。假设 u 是选定的顶点，v 是你的伴侣，我们假装 v 的伴侣不是你，而是一个新创建的顶点 u'。然后 u 是不匹配的，所以我们通过排除 u 来重新设定算法的种子，并在我们随后包含 v 时覆盖新创建的边 u' - v。