一类图的彩虹连通数紧的上界的FPT算法

邓兴超

（天津师范大学数学科学学院，天津 300387）

一类图的彩虹连通数紧的上界的FPT算法

邓兴超

（天津师范大学数学科学学院，天津 300387）

基于divide-and-conquer模式，针对有界树宽度的图设计了一个FPT算法，计算其彩虹连通数紧的上界，该算法是多项式时间可解的.

彩虹连通数；divide-and-conquer模式；FPT算法；树宽度

Chartrand等[1]于2008年提出了图的彩虹连通的概念.G=（V（G），E（G））是简单有限连通图，给图G一个边着色c:E（G）→{1，2，…，n}，n∈N，相邻边可能着同样的颜色.若图G的某条路上的边着不同的颜色，则称这条路为图G的一条彩虹路.如果图G的任意2个点都有一条彩虹路连接，则称图G为彩虹连通的，使得图G为彩虹连通的最少的颜色数称为G的彩虹连通数，记为rc（G）.如果图G的任意2个点都有一条长度为其在G中距离的彩虹路连接，则称图G为强彩虹连通的，使得图G为强彩虹连通的最少的颜色数称为G的强彩虹连通数，记为src（G）.显然有，其中diam（G）为图G的直径.彩虹连通是组合数学中刻画图连通性的连通度概念的一种自然推广.文献[2]证明了对于图G，判断是否rc（G）=2是NP-complete，并且计算rc（G）是NP-hard.文献[3]证明了对于任意的k∈N，判断rc（G）是否小于等于k是NP-hard；即使对二部图判断src（G）是否小于等于k也是NP-hard.一般图是NP-hard的优化问题，对满足某些条件的图类或特殊图类是具有多项式时间算法的.文献[4]得到了包含三角的线图的彩虹连通数，并给出了2类线图的彩虹连通数的紧的上界；文献[5]对极大外平面图给出了计算其彩虹连通数紧的上界的多项式时间算法.

divide-and-conquer方法是一种算法设计模式，其思想就是把问题分解为一些子问题，而这些子问题可以用递归的方法求解，利用这些子问题的解可以求出原问题的解.这个方法在子问题比原问题在本质上小很多的时候是非常有效的.本研究基于divide-andconquer方法对有界树宽度的图设计一个FPT算法，计算其彩虹连通数紧的上界.

首先给出图彩虹连通数的一个重要性质，即如下命题，它在本研究主要结果的证明中起到了决定性的作用.

证明：对k用归纳法来证明此命题.当k=1时命题显然成立.

假设结论对任意的k＜m（m≥2）成立.下面证明结论对k=m成立.

下面证明c是图G的彩虹着色，进而说明命题结论对k=m成立.分3种情形证明对任给的2点x、y∈V（G），在着色方案c下有彩虹路连接它们.

情形1 对于任给的x、y∈V（Gm），显然在Gm的c2着色下有一条彩虹路连接x和y.

情形2 任给2点x、y，x∈V（Gm），y∈V（G）V（Gm）.

图1 情形2（ii）Fig.1 Situation 2（ii）

图2 情形3（ii）Fig.2 Situation 3（ii）

定义 图G=（V，E）的分解树是一个二元对：

这里：Xi，i∈I为V的子集，T是顶点集为I边集为M的一棵树，满足

（2）如果（u，v）∈E，则∃i∈I，使得u、v∈Xi.

（3）对于所有的顶点v∈V，{i∈I|v∈Xi}可以导出一个T的连通子树.

（4）如果i、k、j∈I，并且j在T的从i到k的路上，则Xi∩Xk⊆Xj.

1）、系列平行图（Tw=2）、外平面图（Tw=2）、Halin graphs（Tw=3）等.

定理1[6]任何一个具有n个点的图G的非冗余分解树最多有n个块.

定理2[7]对任意给定的整数k和图G，n=|V（G）|，则存在运行时间为O（2Θ(k3)n）的算法，判断是否Tw（G）≤k，若是，则给出G的一个Tw（G）≤k的树分解.

彩虹路问题（RPP）可描述为：

输入：连通图G，顶点r∈V（G），含l个颜色的图G的一个着色方案cl.

输出：对任给的v∈V（G），找到从r到v（若存在）所有的彩虹路.

设Qv表示cl着色下从r到v所有彩虹路的颜色序列的集合（如果存在），用qv表示Qv的元素，定义yv为cl着色下从r到v的彩虹路的长度，yv是从Qv到{1，…，l}的一个函数Yv=yv（Qv）.设p是彩虹路的前继函数，对任给的一条彩虹路qv的任一点，p给出其前继点.初始化Yv和p意味着设定yr=φ，p（r）=0，qr=φ，qv=φ，yv=l+1，并且对于任意v∈V{r}，有p（v）=-1.综上，解决RPP问题的彩虹路算法（RPA）流程如下：

（1）对于任意一个v∈V（G），初始化Yv、Qv、p.

（2）对于任意一个vi∈V（G），有Yvi、Qvi和p.如果vi有关联边（vi，w），并且其颜色与qvi∈Qvi的颜色不同，则延伸qvi，得到新的彩虹路颜色序列qw=qvi∪{（viw）的颜色}.

下面通过一个例子说明上述RPA算法的有效性.给定一个具有8着色且1个顶点r的图G，见图3.

图3 具有8着色且1个顶点的图GFig.3 Graph G with 8-coloring and 1 vertex

RPA的运行结果见表1.由表1可得，用此算法检验图G的边，考虑RPA算法中r，m-彩虹路对应的参数变化.由m行可得，m有3个前继点，并且有14条彩虹路连接r和m；接着看到m行hm列，第2个颜色序列是246；然后考虑h行，找到相同的颜色序列24；接着看到h行ab列，h的前一个节点是b.通过同样的程序，可得b的前继顶点是r.因此，找到彩虹路rbhm.另外的13条彩虹路也可以通过同样的方式得到.对于任意v∈V（G），所有连接r、v的彩虹路也可以通过同样的方法获得.因为G最多有|V（G）|（|V（G）|-1）/2条边，所以RPA算法在有限时间内是可以结束的.

表1 RPA的输出结果Tab.1 Output results of RPA

引理1 对于任意具有|V（G）|=k+1个点的图G，且G具有用l个颜色的边着色cl，则存在对于边着色cl的蛮力算法，可以得到所有的从r到v的彩虹路（如果存在），对于任意的v∈V（G），算法运行时间不大于g（k，l）=k（l+2k-1l！）.

证明 因为着色方式cl用l种颜色，对于任意的v∈V（G），任意连接r和v的彩虹路长度小于等于l.对任给顶点v∈V（G），连接r和v的i-长度路有i-1个其他点，于是最多需要

条边来检验.从而易得

因此，运行时间最多不超过g（k，l）=k（l+2k-1l!）.

引理2 若|V（G）|=k+1，则可以通过蛮力算法计算图G的彩虹连通数rc（G），其运行时间最多不超

过f（k）=k2（k+1）（k+2k-1k!）.

证明 为了给图G彩虹着色，给图G的一个生成树的边染成不同的颜色，显然k是rc（G）的一个上界，仅考虑1≤l≤k条件下图G的蛮力计算方法.这样，计算rc（G）的运行时间最多不超过

定理3 若G是树宽度为k的简单图，则存在线性时间算法计算图G的彩虹连通数的一个上界，计算所用时间不超过

证明 如果G是一个树宽度为k的简单连通图，f（·）是一个增函数，于是由引理2，对图G的分解树的每一个块，用蛮力算法计算每一个块的彩虹连通数，其运行时间最多是f（k）.由命题和定理1，对树宽度为k的图G，可以在f（k）时间内计算rc（G）的一个上界.因此，结合定理2，对于任给的简单连通图G，都存在线性时间算法，此算法取决于Tw（G）是否小于等于k，如果可以得到图G的一个分解树满足Tw（G）≤k，则可以计算rc（G）的一个上界，算法运行时间最多不超过

下面说明本研究算法给出的rc（G）的上界是紧的.图4（b）是由n个图4（a）构造而成的，其直径为2n，树宽度为2.利用本研究算法得到图4（b）的彩虹连通数的一个上界是2n，显然2n是图4（b）的彩虹连通数.

图4 diam（G）=2n，Tw（G）=2，rc（G）=2nFig.4 diam（G）=2n，Tw（G）=2，rc（G）=2n

下面总结本研究关于计算简单连通图彩虹连通数紧上界的算法：

输入：图G和整数k.

输出：rc（G）的上界.

第1步：利用Bodlaender算法找树宽度不超过k的图G的分解树（如果存在）.

第2步：对图G的分解树的每个块利用RPA算法计算其彩虹连通数.

第3步：用命题和定理3获得图G的彩虹连通数rc（G）的上界.

注 本研究算法对于强彩虹连通数是无效的，因为在决定整个图的彩虹连通数时测地距离是无法判断的.

[1]CHARTRAND G，JOHNS G L，MCKEON K A.Rainbow connection in graphs[J].Math Bohemica，2008，133：85-98.

[2]CHAKRABORTY S，FISCHER E，MATSLIAH A，et al.Hardness and algorithms for rainbow connectivity[J].J Comb Optim，2011，21（3）：330-347.

[3]ANANTH P，MEGHANA N，KANTHI K S.Rainbow connectivity：Hardness and tractability[C]//IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science，Mumbai，2011.

[4]LI X L，SUN X F.Upper bounds for the rainbow connection numbers of line graphs[J].Graphs Combin，2012，28（2）：251-265.

[5]DENG X C，XIANG K N，WU B.Polynomial algorithm for sharp upper bound of rainbow connection number of maximal outerplanar graphs[J]. Appl Math Lett，2012，25（3）：237-244.

[6]KLEINBERG J，TARDOS É.Algorithm Design[M].New Jersey：Addison Wesley，2005.

[7]BODLAENDER H.A linear time algorithm for finding tree decompositions of small treewidth[J].SIAM J Comput，1996，25：1305-1317.

（责任编校 马新光）

FPT algorithm for sharp upper bound of rainbow connection numbers of a kind of graphs

DENG Xingchao
（College of Mathematical Science，Tianjin Normal University，Tianjin 300387，China）

Based on the model of divide-and-conquer，an FPT algorithm for sharp upper bound of rainbow connection numbers of graphs with bounded treewidth is designed，and the algorithm is solvable in polynomial time.

rainbow connection number；model of divide-and-conquer；FPT algorithm；treewidth

O157.1

A

1671-1114（2016）05-0009-04

2015-09-28

天津师范大学博士基金资助项目(52XB1206).

邓兴超（1980—），男，讲师，主要从事图论和组合数学方面的研究.