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

(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)。……