顶点覆盖
一个顶点覆盖的图 是一组顶点, ,这样每边都在 至少有一个顶点在 作为一个端点。这意味着图中的每个顶点都至少接触到一条边。顶点覆盖是一个主题图论它在匹配问题和优化问题。对于需要将图中的所有边都包含在解中的问题,顶点覆盖可能是一种很好的方法。
假设你有一个有许多走廊和转弯处的艺术画廊。你的画廊陈列着非常珍贵的画作,你想确保它们的安全。你们打算在每个走廊安装监控摄像头,这样摄像头就能拍到每一幅画。如果走廊里有摄像头,它就能看到走廊里的每一幅画。如果在两个走廊交汇的角落(转角)有一个摄像头,它可以看到两个走廊的画。我们可以将这个系统建模为一个图,其中的节点表示走廊相遇的地方,或者当走廊变成死胡同时,边缘是走廊。
在这个图中,显示你将放置相机,这样所有的画都被覆盖-这是一个顶点覆盖!(有很多解决方案)。
有很多可能的解决方案——这里有一些。第一个是一个简单的解决方案——在所有节点上安装摄像头。根据定义,这是一个顶点覆盖,因为图中的所有边都必须连接到覆盖中的至少一个顶点。
顶点覆盖
一个图的顶点覆盖 是一组, 的顶点 这样每一个边缘 至少有一个顶点在 作为一个端点。这意味着图中的每个顶点都至少接触到一条边。顶点覆盖是一个NP因为任何解决方案都可以在多时间内验证 检查所有边,看它们的端点是否包含在提议的顶点覆盖中。
下面是显示顶点覆盖的图片。图中的每个红色顶点组成了图的顶点覆盖。每个图中所有红节点的集合都接触图中的每一条边。
通过证明,可以证明顶点覆盖是np完全的3坐是可约顶点覆盖(并通过Cook-Levin定理,这证明了np完整性)。然而,在二部图中,可以在多项式时间内找到一个顶点覆盖。
最小顶点覆盖
的顶点覆盖数也被称为最小顶点覆盖数最小顶点覆盖的大小是 并表示 .
下面是一些最小顶点覆盖的例子,其中最小顶点覆盖中的节点是红色的。
寻找最小顶点覆盖是一个经典的优化问题赋权问题。事实上,顶点覆盖问题是其中之一卡普的21个np完全问题因此是一部经典之作非完全多项式的问题复杂性理论.
例如,在介绍中关于安全摄像头的例子中,也许画廊老板想要最小化安装摄像头的成本,因此想要购买尽可能少的摄像头,同时仍然覆盖所有的画作。在这种情况下,需要一个最小的顶点覆盖。
计算顶点覆盖
有几种确定顶点覆盖的算法。这里是一个伪代码描述的算法,给出了一个近似的顶点覆盖使用的思想,从匹配和贪心算法.由于顶点覆盖问题是np完全的,要得到精确的答案是非常困难和耗时的。很多时候,近似算法是有用的。这些算法比精确算法运行得快得多,但可能产生一个次优解。这是一个顶点覆盖的近似算法。
1 2 3 4 5 6 7 |
|
基本上,算法的工作原理是在 并将每条边的至少一个端点添加到覆盖的顶点集合中 .最优答案将包含匹配中每条边的一个顶点,但次优覆盖可能包含每条边的两个端点,因此覆盖集 可能是最优答案的两倍。该算法适用于处理加权图。
这是一个运行的多项式时间近似算法(因为它不能保证返回最佳顶点覆盖) 时间。
应用程序
与顶点覆盖相比,一些使用顶点覆盖思想的问题具有额外和/或修改的约束条件。下面是一个使用相当直接的顶点覆盖方法的问题。
旅行销售员的问题
旅行销售员问题是图论和复杂性理论中讨论的一个经典的计算机科学问题,特别是在讨论np完全问题时。出差销售员的问题是这样的:
销售人员需要访问一组城市来销售他们的商品。他们知道他们需要去多少个城市,以及每个城市之间的距离。销售人员应该按照怎样的顺序访问每个城市,只访问一次,以减少他们的旅行时间,并在他们的原籍城市结束他们的旅程?
这里有一个旅行销售人员问题的例子,销售人员需要从出发地城市旅行到另外三个城市,然后返回出发地。销售人员必须选择与他们相关的收费道路,并且他们想要最小化他们的旅程成本——因此他们需要找到具有最小边权值的路径。
参考文献
- ,M。Vertex-cover.svg.检索自2016年7月3日https://en.wikipedia.org/wiki/File:Vertex-cover.svg
- ,M。Minimum-vertex-cover.svg.检索自2016年7月3日https://en.wikipedia.org/wiki/File:Minimum-vertex-cover.svg