bipartite - 如何将 SPOJ Quest4 转换为最小顶点覆盖

Question

以下是Maximum Bipartite匹配问题：http ://www.spoj.com/problems/QUEST4/ 通过论坛我知道这个问题可以转换为Minimum Vertex Cover问题，然后可以通过Maximum解决双向匹配。但是，我不明白问题是如何转换为最小顶点覆盖的。请帮助我理解这一点。

Answer 1

令 C , R 是所有行和所有列的集合。现在让 G 是一个在 C 和 R 之间有边的二分图，如果在第 i 行和第 j 列中有一个洞，则从 C 到 R 有一条边 (i,j)。

现在考虑这个图的顶点覆盖。图的顶点覆盖是最小的节点集，这样所有边都被覆盖（每条边都入射到顶点覆盖中的至少一个顶点上）。

在我们的问题图中，每条边代表一个洞。顶点代表行或列。目标 - 在覆盖所有孔的同时最小化块，
相当于 -
在覆盖所有边缘的同时最小化顶点。