算法: Vertex Cover & Independe

这两个东西其实是互斥的关系，而这两个东西的应用也是十分有趣的。

Vertex Cover

先来说说什么是 Vertex Cover，其实就是节点的集合，这些节点将最大地包含图里的所有边，更恰当的名字应该是 Minmum Vertex Cover，以选最少的节点来囊括所有的边。以下图为例

其中红色圈出来的节点就是 Vertex Cover。

Independent Set

再来说说 Independent Set，这也是节点的集合，一般是指 Maximum Independent Set，是说找到最多的节点，这些节点都不是相邻的。

再以上图为例，没有红色圈出来的节点都是 Maximum Independent Set。

由此我们可以得出一个结论

二分图里找 VC 和 IS

在如下二分图中怎么才能找到 Minimum Vertex Cover 和 Maximum Independent Set 呢？其实只要解决一个就可以了，剩下的那个就是所有节点减去前者节点即可。

要解决这个问题，我们要用到最大流和最小割的知识。首先添加 S 和 T，并将它们与各自两边连接起来。

其中每条边的权重都为 1。找到这个图的最大流和最小割如下

原来属于 S 那边如果被分到了 T 这边就是 Vertex Cover 的一员，反之亦然，所以我们可以得到 Vertex Cover 的集合是右上角的节点和左下角的节点，而剩下的节点就属于 Independent Set。

上面就是如何在二分图里找 Vertex Cover 和 Independent Set 的过程。

应用

现在来真正地就用 Vertex Cover 和 Independent Set。假如现在有如下图形

要求：怎么切割才能使得切出来的长方形数量最少呢？

首先我们只切割“有两个角”的部位。

用这些切割后的边画成二分图，将切边看成节点，只要两条切边相交就画一条边将两个切边连起来。

然后在这个二分图里找 Vertex Cover 和 Independent Set，找出来的 Independent Set 数目再加 1 就是切割最少的数目。为什么要加 1 呢，因为如果用 Independent Set 数量去切还会剩下一个 "L" 形结构，所以还需要额外的一刀才能保证切出来的是长方形。