4-正则图上的最小连通顶点覆盖问题

许梦宇，张 安，陈 永，陈光亭

(1.杭州电子科技大学理学院，浙江 杭州 310018；2.台州学院电子与信息工程学院，浙江 台州 318000)

0 引 言

图G=(V,E)的一个顶点覆盖是一个顶点子集VC⊆V，使对每一条边e=(vi,vj)∈E，都满足VC∩{vi,vj}≠∅。顶点数最少的顶点覆盖称为最小顶点覆盖(vertex cover，VC)，最小顶点覆盖问题是一类经典的组合优化问题[1]。如果F不仅是图G的顶点覆盖，而且其导出子图G[F]是连通图，则称F为一个连通顶点覆盖。最小连通顶点覆盖(connected vertex cover，CVC)问题最早由M.R.Garey和D.S.Johnson提出[2]，在无线通信网络设计上有实际应用。

1 定义与性质

首先给出割点(cutvertex)、块(Block)、块图、i-块树等定义。

定义1给定简单连通图G=(V,E)及顶点v∈V，如果G-v不连通，则称v为G的一个割点。一个没有割点的图称为2-连通图。

定义2给定简单连通图G=(V,E)，G的一个极大2-连通子图称为一个块。显然G可以由它的块合并构成，且块与块的交点就是原图G的割点。

定义3给定简单连通图G=(V,E)，构造G的块图TB(G)如下：

(1)顶点由G的块与割点构成；

(2)如果一个块包含了某个割点，则在块图中为它们添加一条关联边。

由文献[13]可知，一个简单连通图的块图必是一棵树，所以通常又称为G的块树。图1(a)—(c)给出了G及其割点、块和块图的示例。在简单连通图G的块树TB(G)上进行缩并和简化操作，可得仅与原图G中的i度割点有关的树，称为G的i-块树，如图1(d)所示。

图1 图G及其割点、块、块图、4-块树

定义4给定简单连通图G=(V,E)，构造块树TB(G)并进行以下操作：

(1)将TB(G)中与图G的非i度割点关联的边缩并；

(2)在缩并后的图中删去环和多重边，得到的简单图即为G的i-块树。

对于最大度不超过4的简单连通图，文献[11]证明了如下性质。

该性质是对图的边数和顶点数一个估计，是文献[11]为4-正则图上的CVC问题设计近似算法和分析最坏情况界的关键，以下给出一个更精确的估计。

证明首先，由于F中所有度为4的顶点都是割点，因此F的4-块树T4(F)上保留了所有度为4的顶点。记λ(F)和μ(F)分别为F中度为4和3的顶点数。为排除平凡情况，不妨认为|V(F)|≥2，下面对λ(F)用数学归纳法证明。

假设结论对任意满足引理条件且λ(F′)≤λ的图F′均成立，即都有

(1)

下面考虑满足引理条件且λ(F)=λ+1>0的图F。

图2 情形1的结构

λ(F)≤μ(F)-4

(2)

同样地，对于归纳假设，如果图F′的每个顶点度数都至少是3，则式(1)等价于

λ(F′)≤μ(F′)-4

(3)

故式(2)得证，即结论对满足引理条件且λ(F)=λ+1>0的图F成立。

故结论对图F也成立。

故结论对图F仍然成立。

综上，根据数学归纳法，引理2得证。

图3 图F中与的3种相对结构

2 近似算法与最坏情况分析

图4 主程序流程

文献[11]对4-正则图上的CVC问题提出近似算法(简称算法A)，算法流程如图4所示。

在分析算法之前，首先指出4-正则图上CVC问题的一个最优解下界。

(4)

对于算法A，考虑以下实例，如图5所示。

图5 算法的一个实例

两虚线之间的结构有k个，从而顶点数|V|=5×2+6k+1=6k+11。算法产生的I为图4中的菱形顶点，即|I|=k+2，所以|VC|=|V|-|I|=5k+9；而最优解VC*是图4中除三角形顶点外(首尾为除菱形顶点外)的其他顶点，从而|VC*|=4k+9。故有

3 结束语