数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法学证明从团问题到顶点覆盖问题的多项式时间归约。
顶点覆盖是指覆盖图中所有边的顶点子集。它用于确定给定图是否具有3SAT到顶点覆盖的归约。
团是指所有顶点都直接连接的顶点子集。它用于确定图中是否存在大小为k的团。
要证明——顶点覆盖可以归约为团问题。
证明
给定一个图G=(V,E)和整数k。
获取其补图G'=(V,E')。
求解CLIQUE(G',|V|-k)。
如果存在解，则返回yes；否则，返回no。
为了证明这种归约，我们需要证明以下几点：
如果VERTEX-COVER(G,k)存在解，则CLIQUE(G',|V|-k)必须存在解，反之亦然。
假设G有一个顶点覆盖V' ⊆ V，其中|V|' = k。那么，对于所有u, v ε V，如果(u, v) ε E，则u ε V'或v ε V'或两者兼有，因为顶点覆盖必须覆盖所有边。
逆否命题是：对于所有u, v ε V，如果u不属于V'，则(u, v) ε/ E，因此(u, v) ε E。
对于任何一对都不在G的顶点覆盖V'中的顶点，它们之间在G中有一条边。
所有都不在V'中的顶点对的并集只是V − V'。因此，根据定义，V − V'是G中的一个团，并且V − V'的大小为|V| − k。
此操作可以在多项式时间内完成。由于VERTEX-COVER可以在多项式时间内归约到CLIQUE，CLIQUE ε NP并且VERTEX-COVER是NP完全的，因此CLIQUE也是NP完全的。
更新于：2021年6月15日
2K+ 浏览量
广告