图的着色问题

图的着色问题第一页，共三十一页，2022年，8月28日一、特例分析1、完全图含有n个结点的完全图是n-colorable2、P5822-colorable第二页，共三十一页，2022年，8月28日2-colorable图G有着色算法？！第三页，共三十一页，2022年，8月28日一、基本技术

本章介绍一个启发式、贪心策略，其运行效果虽然为poorcoloring,但它可以作为下一个复杂算法的子程序，而该复杂算法将使用较少的color第四页，共三十一页，2022年，8月28日

设G=（V，E），其中V=(v1,v2,…,vn

)。第五页，共三十一页，2022年，8月28日1、顺序着色策略

如果vi的邻接点中还没有结点被染成颜色c,则结点着色成c。第六页，共三十一页，2022年，8月28日顺序着色算法SCAlgorithm13.3SequentialColoringInput:G=(V,E),anundirectedgraph,whereV={v1,…,vn}Output:AcoloringofG

seqColor(V,E)intc,i;for(i=1;in;i++)for(c=1;cn;c++)ifnovertexadjacenttovihascolorc：

colorviwithc;break;

continuefor(c)continuefor(i)第七页，共三十一页，2022年，8月28日顺序着色算法的复杂性

最坏情况下为：O(n3)第八页，共三十一页，2022年，8月28日例

P582所有颜色最好为2-colorable所有颜色最坏为

n/2第九页，共三十一页，2022年，8月28日定理13.15

顺序着色方案至多使用了Δ(G)+1种颜色。其中：

Δ(G)表示图G中点的最大度。第十页，共三十一页，2022年，8月28日2、SCI

(Sequentialcoloringwithinterchanges)第十一页，共三十一页，2022年，8月28日

设v1,v2,…,vp-1被着成颜色1，2，…,c(c2)。vp与每一种颜色都有链接。给定任意的1i<jc,Gij是包含被染成i或j颜色的结点以及这些点相互联结的边所构成的子图。第十二页，共三十一页，2022年，8月28日1、如果Gij中所有与vp相连接的连通分支都具有同一种颜色，则“交换颜色”过程停止；

2、否则，对任一个连通分支，如果交换（i,j）这对颜色(如图13.12所示)，则连通分支还是一个2-colorable，v1,v2,…,vp-1还是一个c-colorable.

第十三页，共三十一页，2022年，8月28日

若Gij所有的连通分支都可以分成两类，一类A中与vp有链接的点都染成i颜色，而另一类B中与vp有链接的点都染成j。则把B类（i,j）进行交换。交换之后把vp

染成颜色j。于是SCI少用了一种颜色。SCI可能会改善颜色的使用情况！

是否所有情况SCI都可以比SC少用颜色吗？例如：582页图13.11

第十四页，共三十一页，2022年，8月28日SCI的应用情况与条件

许多情况下SCI效果比SC要好，但也存在反例。第十五页，共三十一页，2022年，8月28日典型事例点集：Vk={ai,bi

,ci|1ik}边集为：1、E={（ai,bj

）,(ai,cj),(bi

,cj)|ij}RSCI（3）=n/9

SSCI（n）=

第十六页，共三十一页，2022年，8月28日二、图的近似着色算法是一个难题

寻找图的一个近似着色算法，它与精确算法的解之比在一个较小的常数范围之内，也是一个难题。第十七页，共三十一页，2022年，8月28日1、定理13.16

：

对任意的图G，如果存在复杂度为多项式的一个图的着色算法，其解小于（4/3

(G)

），则3-colorable问题是一个多项式问题(因为3-colorable问题是一个完全的NP问题，则可以推出P=NP)。第十八页，共三十一页，2022年，8月28日证明：设G是一个3-colorable问题的输入；A是定理13.16中所给出的近似算法。1、如果用A对G着色，且只用了3种颜色，则G是3-colorable；近似算法就是最优算法，即存在3-colorable的最优算法。2、如果所用颜色4，因4不小于（4/3）*3，所以(G)>3,即G不是3-colorable。所以A对G着色只用了3种颜色G是3-colorable，此时A可在多项式范围内求解问题。第十九页，共三十一页，2022年，8月28日2、合成图

(CompositionofGraphs)

设G1=（V1，E1），G2=（V2，E2）,则G1，G2的合成图G(记为G1[G2])=（V，E），其中V=V1×V2，每一个顶点对作为合成图中的一个顶点；边集为E1，E2的“并”，由“本地”和“远程”两类边构成。“本地”边，如（x，v），（x，w）之间有边xV1，vwE2“远程”边，如（x，v），（y，w）之间有边xyE1,v，w可以是V2中任何点。第二十页，共三十一页，2022年，8月28日例P584第二十一页，共三十一页，2022年，8月28日合成图

合成图G1[G2]，包含G2

的多次拷贝，并且相互之间的连通性取决于G1

。第二十二页，共三十一页，2022年，8月28日定理13.17：若存在整数k，对任意的图G,其(G)k

，如果存在复杂度为多项式的一个图的着色算法，其解小于（4/3

(G)

），则3-colorable问题是一个多项式问题。证明：设G是一个3-colorable问题的输入；A是定理中所给出的近似算法，Kk是具有k个顶点的完全图。令H=Kk[G]。

(H)=k*(G)

第二十三页，共三十一页，2022年，8月28日

用A对H着色，1、若G是3-colorable，则：

val(H,A(H))<(4/3)(H)(4/3)3k=4k

则A所使用的颜色数为4k.

2、若G不是3-colorable，至少要4种颜色，因此A至少需要使用4k种颜色对H着色。因此，能否在多项式时间内判断G是否为3-colorable用A对H进行着色时所使用的颜色数是否小于4k第二十四页，共三十一页，2022年，8月28日三、Wigderson近似着色算法第二十五页，共三十一页，2022年，8月28日记号

设vVN(v)：v的所有邻结点所构成的集合

H(v)：由N(v)所得到的子图第二十六页，共三十一页，2022年，8月28日引理

若G是一个k-colorable,则对任意的vV，

H(v)是一个(k-1)–colorable。

证明：反证第二十七页，共三十一页，2022年，8月28日color3算法13.43–colorable的近似算法输入:G为一个3–colorable图；n为图G的顶点输出:染色后的图GColor3(G)intc;c=1;while(Δ(G)n(1/2))LetvbeavertexinGofmaximumdegree;ColorH(v)withcolorscandc+1;Colorvwithcolorc+2;DeletevandH(v)fromG并删除与它们相联的边;c+=2;

用SC对余图着色；第二十八页，共三十一页，2022年，8月28日例P587图13.4第二十九页，共三十一页，2022年，8月28日定理13.19

若G为一个3–color