算法: Vertex Cover & Independent Set

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

Vertex Cover

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

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

Independent Set

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

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

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

Min Vertex Cover 的数量 = 所有节点数 - Max 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" 形结构,所以还需要额外的一刀才能保证切出来的是长方形。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • 我就想问在一个服务器上不同的jar包执行eureka服务注册时,服务名为什么都是demo,导致服务注册失败,为什么...
    潦草心阅读 207评论 0 0
  • 临摹心蓝丫头作品 半成品,等买了高光笔再补完整。同样是没完没了的排线……
    离开的猫_Lin阅读 167评论 0 0
  • 今天是2019年的春节。热闹过后,回到自己的小窝。虽然有些疲惫,但还是非常喜欢这种暇意,静静的听着音乐,看着...
    涛涛青竹阅读 845评论 0 3
  • 我和宝宝异地而居,往往十天半个月才能见上一面,每次都是行也匆匆去也匆匆。 昨天陪宝贝去幼儿园,小家伙不想走...
    美女米豆阅读 263评论 3 4