赞
踩
一,定义
独立集:给定一个图G={V,E}和数k。判定图中是否存在k个两两没有边相连的顶点集。
顶点覆盖:给定一个图G={V,E}和数k。判定图中是否存在k个顶点,使其与所有边相连。
二,证明相互规约
命题:独立集 ≡p 顶点覆盖
对于一个给定的图G={V,E}
(1).证明:当S是G的独立集时,V-S 是G的顶点覆盖。
对于G中的任意一条边(i,j)∈E有,顶点i,j不会同时属于S。即i∉S,或j∉S,或i,j∉S
换一句话就是,i,j顶点至少有一个属于V-S,即i∈V-S,或j∈V-S,或i,j∈V-S.
由(i,j)的任意性可以知道。V-S覆盖了所有边。所以V-S是顶点覆盖。
(2).证明:当S是G的顶点覆盖时,V-S是G的独立集。
对于G中任意一条边(i,j)∈E有,顶点i,j至少有一个属于S。即i∈S,或j∈S,或i,j∈S
换一句话就是,i,j顶点最多只有一个顶点属于V-S,即i∉V-S,或j∉V-S,或i,j∉V-S.
由(i,j)的任意性可以知道。对任意边V-S最多包含了边的一个顶点。所以V-S是一个独立集。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。