当前位置:   article > 正文

独立集和顶点覆盖的相互规约_独立集和点覆盖规约证明

独立集和点覆盖规约证明

一,定义

独立集:给定一个图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是一个独立集。

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Monodyee/article/detail/378692
推荐阅读
相关标签
  

闽ICP备14008679号