《着色问题分析》PPT课件.ppt

图论及其应用,第六章着色问题,图论及其应用,2,6.1边色数,k-边着色（k-edgecoloring）CC是k种色在图G的边集上的一种分配。C是E(G)的一个k-划分，即C=(E1,Ek)边着色C是正常的每个Ei都是G的一个匹配。G为k-边可着色的（k-edgecolorable）G有一正常k-边着色。存在E(G)的一个k-划分C=（E1,Ek），使每个Ei都是G的一个匹配。（注：允许Ei=）显然，G为k-边可着色的G为p-边可着色的(pk).G的边色数（edgechromaticnumber）(G)=minkG为k-边可着色的。G为k-边色的（k-edgechromatic）(G)=k。,图论及其应用,3,6.1边色数,例：n个人举行一些两两会谈，每次会谈用一个单元时间。问最少要多少单元时间，才能安排完所有会谈？解：作一n顶点图G，其中两顶点相邻当且仅当对应的两人间要安排一次会谈。易见，所需时间单元数(G)。称色i表现(represented)于顶点v与v相关联的某一边有色i。,图论及其应用,4,6.1边色数,引理6.1.1设连通图G不是奇圈，则G有一2-边着色，使该二色表现于G的每个度2的顶点。证明：不妨设G为非平凡的。(A)若G为Euler图：若G为一个圈：则G为偶圈，从而G的一个正常2-边着色满足要求。若G不是一个圈：则一定存在顶点v0，使d(v0)4(Euler图每个顶点的度均为偶数）。令v0e1v1e2。ev为G一的Euler环游（v=v0）。令E1与E2分别为Euler环游中下标为奇数与偶数的边子集。则G的2-边着色C=（E1，E2）满足要求。,图论及其应用,5,6.1边色数,(B)若G为非Euler环游：往G中加一新顶点v0，并将v0与G中每个度为奇数顶点都用一新边连起来，得图G。显然，G为一Euler图。令v0e1v1e2ev（v=v0）为G的一Euler环游。与(A)一样定义C=（E1，E2），易见C=(E1E，E2E）满足要求。记号c(v)=边着色C表现于v的不同颜色数。易见，c(v)d(v)vV。C为正常边着色c(v)=d(v)vV。称G的k-边着色C为其k-边着色C的一个改进。C为最优k-边着色（optimalk-edgecolouring）C不能再改进。,图论及其应用,6,6.1边色数,引理6.1.2设C=（E1，。，Ek）为G的一个最优k-边着色。若G中有一顶点u及色i与j，使i不表现于u，而j在u上至少表现2次。则GEiEj中含u的分支是一奇圈。证明：令H为GEiEj中含u的分支。假设H不是奇圈，由引理6.1.1.，H有一2-边着色，使该二色表现于H的每个度2顶点上。以这方式，用色i与j对H重新边着色，得G的一个新的k-边着色C。显然，c(u)=c(u)+1，c(v)c(v)vu，这与C为最优矛盾。,图论及其应用,7,6.1边色数,定理6.1设G为偶图，则=。证明：（Wilson）对进行归纳。当=1时显然成立。假设对n，则=+1；(b)利用(a)证明：若G是从有偶数个顶点的简单图中剖分一条边所得的图，则=+1；若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则=+16.2.4(a)证明：任一无环图G都有-正则无环母图。（注：不一定为生成母图）(b)利用(a)及习题5.2.3(b)证明：若G是无环图且是偶数，则3/2。6.2.5称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。证明：每个唯一3-边可着色的3-正则图都是Hamilton图。6.2.6简单图的积图是指顶点集为V(G)V(H)的简单图GH，其中(u,v)与(u,v)相邻u=u且vE(H)；或v=v且uuE(G)(a)利用Vizing定理证明：(GK2）=(GK2)。(b)试证：若H是非平凡的，且(H)=(H)，则(GH)=(GH)。6.2.7叙述求简单图G的正常(+1)-边着色的好算法。6.2.8*证明2的简单图G有一(-1)-边着色，使得所有-1种色在每个顶点上都表现6.2.9设简单图G有割点，则=+1。,图论及其应用,13,6.2排课表问题,问题m位教师和n个班级，其中教师Xi要给班级Yj上pij节课。欲在最少节次p内排完所有的课。将偶图G=(X,Y,E)的边集E划分成互不相交的p个匹配(E1，Ep)，且使p为最小，其中X=x1,xm,Y=y1,yn求偶图G的p-边着色，其中p=。由习题6.1.4知，上述问题有好算法。当上述问题中教室数有限时（教室数），若要在p（）节内排完全部（l=E）节课，所需教室数c问题能否适当排课，使全部节课在p（）节内排完，且每节课所用教室数？（1ip）,图论及其应用,14,6.2排课表问题,引理6.3设M，N为G的二不相交匹配，且MN，则存在G的二不相交匹配M，N使M=M-1，N=N+1，且MN=MN。证明：令H=GMN，则H的每个分支为一路或圈，由M及N的边交错组成。且由于MN，存在H的一个分支，它是路P，起、止于M边。因此M=ME(P)及N=NE(P)即为所求。定理6.3设G为偶图，p，则存在G的p个互不相交的匹配使E=M1Mp。且,1ip。,图论及其应用,15,6.2排课表问题,证明：由定理6.1,E可划分为个互不相交的匹配M1，M。因此，对p，G有p个互不相交的匹配M1，M，Mp。（令Mi=当ip）使E=M1Mp。今对边数差1的两个匹配，反复使用引理6.3，最后可得所求的匹配M1，Mp。注在实际应用中，教师和班级往往会提出一些，例如所上节次时间的要求，问题变得很复杂。Even，Itai&Shmir（1976）证明：在教师和班级提出条件时，判定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。,图论及其应用,16,6.3顶点着色和色数,正常（顶点）着色（proper（vertex）coluring）每边两端不同色。k-（顶点）着色（k-（Vertex）colouring）k种色在V(G)上的一种分配，且任二相邻（的不同）顶点不同色。V的一个k-划分（V1，Vk）使每个Vi（可为）都是G的一个独立集。k-（顶点）可着色（k-（vertex）colourable）G有一k-着色。显然，G为k-可着色G的基础简单图为k-可着色。由此我们约定，本章只讨论简单图。例：G为1-可着色的G为一空图。G为k-可着色的G为k-部图。G为k-可着色的G为j-可着色的（kj）。,图论及其应用,17,6.3顶点着色和色数,色数（chromaticnumber）(G)=kG为k-可着色的。G为k-色图(G)=k。例：设每一教师只开一门研究生课，每门课课时为一单元。问至少要多少单元才能排完所有课？解：作一图G，每一顶点对应一们课；两顶点相邻当且仅当有一研究生选修对应的两门课。由此，所需单元数(G)。例：设有一些药品存储在一仓库中，其中有些药品是不相容的，不能放在同一房间中，问至少应把仓库间隔成几个房间？G为临界的（crtical）(H)(G)HGG连通且满足(G-e)(G)eE(G)G为k-临界的G为临界图，且(G)=k显然，G为k-色图G包含一k-临界子图。,图论及其应用,18,6.3顶点着色和色数,例。1-临界图K1（唯一）。2-临界图K2（唯一）。3-临界图奇圈。4-临界图例如：K4，Grotzsch图等。注意一图G的临界图不一定是它的导出子图，例如,图论及其应用,19,6.3顶点着色和色数,定理8.1G为k-临界图k-1。证明：反证，假设k-1。取vV使d(v)=。因G为k-临界图的，G-v必是（k-1）-可着色的。令:（V1，Vk-1）为G-v的(k-1)-着色。由于d(v)=k-1，v一定与某一Vj中所有顶点都不相邻。从而（V1，Vjv，Vk-1）是G的(k-1)-着色，于是(G)k-1，矛盾。#,图论及其应用,20,6.3顶点着色和色数,推论8.1.1(G)=kG中至少有k个度k-1的顶点。证明：令H为G的k-临界子图。由定理8.1知dH(v)(H)k-1vV(H)。dG(v)dH(v)k-1vV(H)。又因H为k-色的，必有|V(H)|k。#推论8.1.2对任一图G都有+1。证明：由推论8.1.1知-1。#,图论及其应用,21,6.3顶点着色和色数,令S为连通图G的一个点割。V1，Vn为G-S的各分支的顶点集。称Gi=GViS为G的S分支。称G1，Gn上的各个着色在S上是一致的，当且仅当在各个着色中S中每顶点都被着以相同的色。,图论及其应用,22,6.3顶点着色和色数,定理8.2临界图的任一点割都不是团。证明：反证，假设k-临界图G有一点割S是团。令G1，Gn是G的S分支。因G为k-临界的，每个Gi都必是（k-1）-可着色的。但S为团，每个Gi的任一（k-1）-着色都导致S中所有顶点彼此不同色。从而一定存在G1，Gn在S上一致的（k-1）-着色。这些着色一起构成G的一个（k-1）-着色，矛盾。#推论8.2每一临界图是一个块。证明：若临界图G含一割点v，则v是G的一个点割，且是团。故临界图不含割点，因而是个块。#注：NP-completeprob：对任给图G及正整数k|V|，G是否为k-可着色的？从而，求任给图G的色数是个NP-hardprob.。,图论及其应用,23,6.3顶点着色和色数,贪心（greedy）着色法：用色1，2，逐步（按某一顶点排序）一个个顶点进行正常着色，每次选用尽可能小的颜色进行着色。例如，对任给图G，按任一顺序进行贪心着色，则每当尝试对某一顶点v着色时，其邻集N(v)中至多出现种色，因此总可从+1种色中挑选一色着在v上。整个着色至多用了+1种色，故G为(+1)-可着色的。从而得到推论8.1.2的另一证明。显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图G的一个-着色为C=（V1，V2，V）。按(V1，V2，V)的顺序任作一顶点排序（同一色集Vi内随意排序），按此顺序进行贪心着色，易见，一定恰好用了个色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到关于着色的一个较好结果（如Brooks定理之证明）。下面是这方面的一些结果：,图论及其应用,24,6.3顶点着色和色数,例。设图G中度序列满足：d1d，则证明：不妨设顶点排序：v1，v恰使d(vi)=dii=1,2,.,。沿进行贪心着色。不妨设某vk被着上了色。易见，它一定与前面-1个不同色的顶点相邻，因此dkd(vk)-1。又，显然k。mindk+1，k得证。#例。试证：(G)1+max(H)|H为G的导出子图。证明：作G的顶点排序：v1，v如下：v为图G的最小度顶点；v-1为图G-v的最小度顶点；v为图G-v，v-1的最小度顶点；s令L=max(H)|H为G的导出子图。注意到G，G-v，G-v，v-1，都是G的导出子图，因而每个dH(vi)L。于是每个vi都只与前面L个顶点相邻，从而贪心着色法至多用了L+1个色。故(G)1+L=1+max(H)|H为G的导出子图。#,图论及其应用,25,6.3顶点着色和色数,注:顶点着色问题的另一常用技巧是基于以下显而易见的命题：设d(u)k-1(k2)uUV，而G-U为k-可着色的，则G也是k-可着色的。(从而，当尝试G是否为k-可着色时，可先不管（先逐步删去）所有度k-1的顶点。)由上知：若d(u)(G)2则(G-u)=(G)例:试证(G)+(Gc)=+1。证明：对进行归纳。当2时，显然成立。假设对顶点数时都成立，而(G)=。情况1当(G)(G)-1时：则(Gc)=-1-(G)-(G)(Gc)(Gc)+1-(G)+1，得证情况2当(G)(G)-1时：取u使dG(u)=(G)(G)-2因此，首先有(G1)=(G)其中G1=G-u。由归纳假设知，(G1)+(G1c)=(G)+(Gc)=(G1)+(Gc)(G1)+(G1c)+1=+1#,图论及其应用,26,6.3顶点着色和色数,8.1.1.证明：若G是简单图，则2/(2-2)。8.1.2.证明：若G的任二奇圈都有公共顶点，则5。8.1.3.证明：设图G中度序列满足d1d，则8.1.4.利用习题8.1.3证明：(a)(b)(G)+(Gc)=+1。(c)推论8.1.1。8.1.5.试证：(G)1+max(H)|H为G的导出子图。8.1.6.*设k-色图G上有这样一个正常着色（不一定为k-着色），其中每种色都至少分配给两个顶点。证明：G也有这样的k-着色。8.1.7.证明：若C=（V1，V2，V）是图G的一个-着色，则每一Vi都含一顶点vi，它与其他每个Vj(ji)至少有一边相连。8.1.8.若G的任二k-着色都导出V的相同的k-划分，则称G为唯一k-可着色的。证明：k-临界任一顶点割的导出子图不会是个唯一(k-1)-可着色子图。,图论及其应用,27,8.1色数习题（续）,8.1.9(a)证明：若u、v为临界图的二顶点，则不可能有N(u)N(v)。(b)试证：不存在恰有k+1个顶点的k-临界图。8.1.10.(a)(G1G2)=(G1)+(G2)，其中G1G2称为图G1与G2的联图，它是将它们间的每对顶点都用新边连起来所得的图。(b)G1G2是临界图，当且仅当G1与G2都是临界图。8.1.12.设G1与G2是恰有一公共顶点v的k-临界图，且vx和vy分别是G1和G2的边，则(G1-vx)(G2-vy)+xy也是k-临界图。8.1.13.对n=4及n6构造n个顶点的4-临界图。8.1.14.*(a)设V的2-划分（X，Y）使GX和GY都是n-可着色的，且边割X，Y最多有n-1条边，则G也是n-可着色的。(b)试证：每个k-临界图都是(k-1)-连通的。(提示(a)：令(X1,X2,Xn)及(Y1,Y2,Yn)分别是GX和GY的n着色。作一偶图H=(x1,x2,xn,y1,y2,yn,E)，使xiyjE边割Xi,YjG=。利用习题5.2.6(b)证明H有完美匹配。由此构造G的n-着色。）,图论及其应用,28,8.1色数习题（续）,8.1.15.求(Kne)及(Kne1-e2)，其中e、e1、e2都是Kn的边，且后两者互不相邻。8.1.16.任一4-可着色简单图G的边都有一红、兰2-边着色，使G中每一三角形都恰含一红边及二兰边（提示:令所用4色为0、1、2、3。对每边e=xy，令色(e)=色(x)+色(y)(mod2)）8.1.17证明：奇圈数2的图一定是3-可着色的。8.1.18证明：。8.1.19设e为简单图G的任一边，则(Ge)=min(G),(Ge)。,图论及其应用,29,8.2Brooks定理,图论及其应用,30,8.3定理8.4,定理8.4设简单连通图G不是奇圈或完全图，则。证明：对进行归纳。当3时，显然成立。假设当n时都成立，而(G)=n。不妨设：G为-正则的。（不然，取u使d(u)=，由归纳假设，易见，G-u为-可着色的，从而G亦然。）G为2-连通的。（不然，令v为G的割点，由割点定义，存在E的2-划分（E1，E2）使GE1与GE2恰有一公共顶点v，从而易见，结论成立。）3。（不然，G为圈，结论成立。）今选取3个点x1，x2，xn如下：若3，则任取一点为xn，并取N(xn)中任二不相邻顶点作为x1与x2。（这样的二顶点一定存在。不然，N(xn)xn是一团，从而易见G是完全图，矛盾。）若=2，则选取xn使(G-xn)=1。注意到G-xn中至少有两个为endklocks（即，它是G的块，且其顶点中只有一个是G的割点），它们每个至少含一G的非割点与xn相邻接。取不在同一endklock中的两个这种顶点作为x1与x2。,图论及其应用,31,8.3定理8.4,在上述两种情况下，我们都有：G-x1,x2连通；且xnx1，xnx1E(G)而x1x2E(G)下面我们由此来作V的一个排序：取xn-1Vx1,x2,xn使xn-1N(xn)；取xn-2Vx1,x2,xn-1,使xn-2N(xn-1,xn)；由于G-x1，x2是连通的，上述步骤可一直进行到底，得V的一个排序：x1，x2，xn。其中每个xi（ii，相邻接。又，x1与x2不相邻。于是，贪心着色法只用了个色。#,图论及其应用,32,习题,8.2.1.证明Brooks定理等价于下述命题：若G是k-临界图（k4），且不是完全图，则2(k-1)+1。8.2.2*.利用Brooks定理证明：若G是=3的无环图，则4。,图论及其应用,33,8.4围长和色数,易见，若G中最大团的顶点数k，则k。下面的定理表明，一个有很大色数的图，其最大团的顶点数不一定也很大。定理8.7对任正整数k，都存在不含3-圈的图G使(G)=k。(即，可找到色数任意大的图，但其最大团顶点数却只为2。)证明：对k进行归纳。当k=1时，G1=K1满足要求；当k=2时，G2=K2也满足要求；一般，设Gk=(Vk,Ek)，Vk=v1，vn满足要求（k2），则由Gk构造Gk+1=(Vk+1,Ek+1)如下：(1)添加新顶点u1，un及v；(2)把每个ui连到vi（在Gk中）的每个邻点；(3)再将v连到每个uj。易见，Gk+1中不含3-圈。又，Gk的任一k-着色可扩充成Gk+1的（k+1）-着色如下：将每个ui着以vi上的色；再用一新色着在v上。显然，这是Gk+1的正常（k+1）-着色，从而Gk+1是（k+1）-可着色的。余下只要再证Gk+1不是k-可着色的即可：不然，不妨设在该k-着色中v被着以色k。这时无一ui被着以色k。今，将每个被着以色k的顶点vi都改着以顶点ui的色。易见，这是Gk+1的正常k-着色。它导致Gk的一个正常（k-1）-着色，这与Gk为k色图相矛盾。#,图论及其应用,34,8.4围长和色数,注：Hajos(1961年)曾提出似乎是可信的猜想：G为k-色图G包含Kk的一个剖分。当k=3及4时可证1猜想成立。但1986年（JurnalsofGraphTheory,vol.3,p314）已证明该猜想不成立。,图论及其应用,35,8.4围长和色数习题,8.3.1.证明：定理8.7中的图Gk是一k-临界图。8.3.2*(a)设G是围长至少为6的k-色图（k2）。作一新图H如下：取k个新顶点集S及G的个互不相交的拷贝，且建立G的拷贝与S的元子集之间的一一对应。再将G的每个拷贝的顶点和与它相应的S的元子集的元素用一匹配连接起来。证明：H的色数至少为k+1，其围长至少为6。(b)试证：对任k2，都存在围长为6的k-色图。（提示(a)：易证H的围长至少为6。若H为k-可着色的，则存在S的元子集，其元素都染有相同的颜色。再考察对应的G的拷贝得出矛盾。）,