边着色图上最大弱适当树问题近似算法

金世豪，陈光亭，陈 永，张 安

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

0 引 言

图的着色理论是图论的重要分支之一，是图论研究中最活跃的方向之一。边着色图上的生成树问题在生物信息学、网络设计和网络通信等领域中有着重要应用[1]。边着色图上的生成树问题可以从实际问题中提炼出普适性的理论问题，使用数学的形式表达设计高效算法以解决问题。图着色中最基本的问题是把颜色分配给边，相邻的边着不同的颜色。

早期关于边着色图的研究工作都是考虑每对边颜色都不相同的生成树问题即彩虹生成树[2-4]，文献[5-6]证明了完全图或完全二部图的任意边着色中多种颜色生成树的存在性；文献[7]指出，当顶点的邻边颜色数大于等于顶点个数一半时，存在适当生成树；文献[8]指出，增加颜色的个数，边着色中存在适当路径和适当圈的概率越大；文献[9]给出了在边着色图中，把单色子图顶点划分的方法。最近关于边着色图中适当边着色(Proper Edge-colored)问题，文献[10]给出了没有适当着色圈的完全边着色图的算法，此算法的时间复杂度为O(n2)，同时证明了当颜色数c≥2时，最大弱适当树(Maximum Weak Proper Tree，MWT)问题是NP-hard。基于此，本文重点研究颜色数c=2时求解最大弱适当树问题的近似算法设计及其理论分析。

1 边着色图上最大弱适当树问题

定义1设T是边着色图Gc的1个子图，将子图边着色，使得每个顶点的邻边着不同的颜色。如果子图为1个路径，则称为适当路径(Proper Path)。

定义2如果子图是1棵树，即这个子图是连通且无圈子图，当子图覆盖Gc的所有顶点则称树为Gc的生成树，在生成树上固定一个顶点为树的根，根到树的任何叶子都是适当路径，但树顶点的邻边能着相同颜色，则称为弱适当树。

对于边着色图Gc，在图Gc上找到包含顶点最多的弱适当树，这一问题称为最大弱适当树(Maximum Weak Proper Tree，MWT)。下面给出1个颜色数c=2的边着色图例子。

给出3层结构的边着色图Gc的例子如图1所示，本文所有图中虚线代表红线，实线代表蓝线。图1中，第1层只有1个根节点r，第2层每2个顶点ai1,ai2(i∈{1,…,s},s=6)为一组，ai1,ai2之间有边并随机着红或蓝1种颜色，组与组之间没有边，根r到每1组的2个顶点ai1,ai2(i∈{1,…,s})都有边，所有的从根r到ai1,ai2(i∈{1,…,s})的边随机着红或蓝1种颜色，根r与每2个顶点ai1,ai2构成1个三角形，因此有s个这样的三角形。因为只能选取其中2条边，所以共有以下3种组合：{rai1，rai2}，{rai1，ai1ai2}，{rai2，ai2ai1}。第3层有n个顶点(c1,c2,…,cn)，每个顶点只能和任意3个三角形有边，且只能连接每个三角形第2层的1个顶点，边的颜色以相同的概率着红或蓝其中1种颜色。

图1 s=6时，3层结构图Gc

2 MWT问题的算法设计与分析

通过研究图1的结构，以贪婪迭代为基础得到求解MWT问题的近似算法——贪婪算法GA。贪婪算法GA是1个多项式时间的近似算法，其主要步骤如下。

(1)选择顶点r为生成树T的根。

(2)进行预处理。依据三角形3种可能组合：{rai1,rai2},{rai1,ai1ai2},{rai2,ai2ai1},删除第2层与第3层之间不可行的边，即删除不能连接上述3种情况中的任意1种的边。

(3)选取点。生成树T选取第2层的所有点；对每个三角形的3种组合，选择连接到第3层顶点数量最多的组合到生成树T中，以及选取所连接的第3层的顶点到生成树T中。

(4)重复步骤3，直到到s个三角形所对应的s个组合都出现在生成树T中，算法停止。

(5)输出T。

图2 三角形结构

证明因为边着色的颜色只有红蓝2种颜色，所以三角形有2种结构，如图2所示。

综上，引理1得证。

图3 三角形可能组合

证明对实例I进行预处理之后，用nj表示前j个三角形与第3层相邻顶点个数总和(ns=n),nij表示第j个三角形与前i个三角形共有顶点个数(i

(1)

(2)

当s=k-1时，则有

(3)

综上，引理2得证。

定理1贪婪算法GA的最坏情况界为2，且该界是紧的。

下面通过1个紧例来验证贪婪算法GA的最坏情况界为2。通过贪婪算法GA删去不可选取的边得到实例如图4所示，第1层1个顶点r，第2层的顶点为ai1,ai2(i∈{1,2,3,4,5,6})，第3层共有4n-4个顶点。把第3层的所有顶点分成8个顶点族，分别为A，B，C，D，E，F，G，H。

图4 贪婪算法GA的紧例

根据贪婪算法GA从第1个三角开始遍历，选取{ra11,ra12}，因为B和C的顶点族加起来大于A和D的顶点族，所以选取{ra21，a21a22，a21B，a22C}，依次下去算法解为{ra31,ra32}，{ra41,a41a42,a41F,a42G}，{ra51,ra52},{ra61,ra62}，共13+2n个顶点，即GA(I)=13+2n，而最优解可以选取到全部顶点共OPT(I)=13+4n-4。

3 结束语

本文提出了顶点个数最多的边着色图上弱适当树问题的多项式时间近似算法，并证明算法的最坏情况界为2。边着色图的图结构以及着色的颜色数是设计近似算法和得到最坏情况界的关键因素，后续将针对这2个因素，即在颜色数为一般情况、图结构是完全图或二部图时，对边着色MWT问题近似算法的设计展开进一步研究。