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

图论及其应用,第六章 着色问题,图论及其应用,2,6.1 边色数,k-边着色（k-edge coloring）C C是k种色在图G的边集上的一种分配。C是E(G)的一个k-划分，即 C=(E1,Ek)边着色C是正常的 每个Ei都是G的一个匹配。G为k-边可着色的（k-edge colorable）G有一正常k-边着色。存在E(G)的一个k-划分 C=（E1,Ek），使每个Ei 都是G的一个匹配。（注：允许Ei=）显然，G为k-边可着色的 G为p-边可着色的(p k).G的边色数（edge chromatic number）(G)=min kG为k-边可着色的。G为k-边色的（k-edge chromatic）(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图每个顶点的度均为偶数）。令 v0 e1 v1 e2。e v 为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图。令v0 e1 v1 e2 e v（v=v0）为G的一Euler环游。与(A)一样定义 C=（E1，E2），易见C=(E1 E，E2 E）满足要求。记号 c(v)=边着色C表现于v的不同颜色数。易见，c(v)d(v)v V。C为正常边着色 c(v)=d(v)v V。称G的k-边着色C 为其k-边着色C的一个改进。C为最优k-边着色（optimal k-edge colouring）C不能再改进。,图论及其应用,6,6.1 边色数,引理6.1.2 设 C=（E1，。，Ek）为G的一个最优k-边着色。若G中有一顶点u及色i与j，使i不表现于u，而j在u上至少表现2次。则GEi Ej 中含u的分支是一奇圈。证明：令H为GEi Ej 中含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 时显然成立。假设对 k(2)都成立，而(G)=k。任取G的一边 e=uv，考虑 G=G-e。由归纳假设，G 有一(G)-正常边着色 C=E1,.,E(G)。若(G)(G)，则G显然有(G)-正常边着色，证完；否则，(G)=(G)。令Au与Av各表示C中不表现于u与v的色集。由于在G中u与v都不是其最大度顶点，从而有Au,Av 当 Au Av 时：将Au Av 之一色着在边e上，即得G的(G)-正常边着色。Au Av=时：任取色i Au 及色j Av。令H为GEi Ej 中含u的分 支。易见，H是一条路，由色i与色j边交替组成。因此，v一定不在H上（不然，由于H的第一条边有色j，最后一边有i，其长为偶数。这导致G中含一奇圈H+e，矛盾。）对换H上的色i与j，得G的另一正常(G)-边着色，其中在u与v上色j都不表现。再将色j着在e上，即得G的正常(G)-边着色。,图论及其应用,8,6.1 边色数习题,6.1.1 找出一适当的边着色以证明(Km,n)=(Km,n)。(a)证明：任一偶图G都有一-正则偶母图。（不一定为生成母图！）(b)利用(a)给出定理6.1 的另一证明。叙述求偶图G的正常-边着色的好算法。6.1.4*证明：若偶图G有 0，则G有一-边着色，使所有 种色在每一顶点上都表 现。每一简单、3-正则、H-图，都有=3。6.1.6(Issacs引理)设G为3-正则图，且其上有一3-边着色，则在G的任一边割中(任 S V)，3-种色边的奇偶性相同。（提示：考虑GEi Ej，ij，其中C=(E1,E2,E3)为G的3-边着色）,图论及其应用,9,6.1 Vizing定理,定理6.2(Vizing,1964)对简单图G有=或+1。证明：（Bollobas证法）不妨设G中 除边uv1外 都已用色 1,2,+1进行了正常边着色。下文中我们恒用Ei表示G中全体色i边的集合。注意到，G的每个顶点上都至少有一色未表现。令顶点u，v1 上各有色i0，i1 未表现。我们可逐步找到不同的色、边序列：i0，i1，i2，ij，；uv1，uv2，uv3,，uvj，。其中，色ij 是顶点 vj 上未表现的（任意取定的）一色；边uvj 上有色ij-1。j=2，3，。显然，上述过程至多进行到某q（）次而停止（无法继续满足上述条件）。这时只有两种可能：(A)色iq 未表现于顶点u上（即没有一条u的关联边有色iq）：重新进行边着色如下，uvj 改着色ij 1 j q-1并抹去边uvq 上的色 iq-1。得G中除uvq外的正常（+1）边着色。其中u与vq上色iq 同时不表现。将uvq 改着色 iq 即得G的正常（+1）边着色。,图论及其应用,10,6.2 Vizing定理,(B)iq=ik 某 1 k q-1：重新进行边着色如下，将uvj 改着色ij 1 j k 并抹去边uvk+1 上的色 ik。易见，H=的每个分支是路或圈，由色i0与ik的边交错组成，且 u，vk+1，vq 在H中的度 1。从而，该三顶点不可能同时在H的一分支中。这时以下二情形至少有一个为真，u 与vk+1不在H的同一分支中：将H的含vk+1 分支中的色i0 与ik对换，得G 的除uvk+1外的正常（+1）-边着色，其中u与vk+1上色i0都未表 现。从而，G有一正常（+1）-边着色。u与vq不在H的同一分支中：再继续调整边着色如下，将uvj 改着色ij k+1 j q-1 并抹去边uvq上的色（iq-1）易见，上述更动并未涉及色i0与ik，因此H 保持不变。将H中含vq分支的色i0 与 ik 对换，得G 的除uvq外的正常（+1）-边着色，其中在u与vq上色i0都未表现。从而，G有一正常（+1）-边着色。,图论及其应用,11,6.2 Vizing定理,注1 对一般图有Vizing定理 设G为无环图，则+，其中是G的重数（连接G中每一 对顶点上的最大边数）。注2 NP-complete prob：已给简单图G，是否有=？注3“2-边连通、3-正则、简单、平面图都有=3”“4-色猜想成立”。,图论及其应用,12,6.2 Vizing定理习题,6.2.1*找出适当的边着色以证明(K2N-1)=(K2N)=2n-1。6.2.2 为奇数的非空正则简单图G有=+1。(a)设简单图G中=2n+1且 n，则=+1；(b)利用(a)证明：若G是从有偶数个顶点的简单图中剖分一条边所得的图，则=+1；若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则=+1(a)证明：任一无环图G都有-正则无环母图。（注：不一定为生成母图）(b)利用(a)及习题5.2.3(b)证明：若G 是无环图且 是偶数，则 3/2。称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。证明：每个唯一3-边可着色的3-正则图都是Hamilton 图。6.2.6 简单图的积图是指顶点集为V(G)V(H)的简单图GH，其中(u,v)与(u,v)相邻 u=u且v E(H)；或 v=v且uu E(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=。由习题知，上述问题有好算法。当上述问题中教室数有限时（教室数），若要在 p（）节内排完全部（l=E）节课，所需教室数c 问题 能否适当排课，使全部节课在p（）节内排完，且每节课所用教室数？（1 i p）,图论及其应用,14,6.2 排课表问题,引理6.3 设M，N为G的二不相交匹配，且MN，则存在G的二不相交匹配M，N使M=M-1，N=N+1，且M N=M N。证明：令H=GM N，则H的每个分支为一路或圈，由M及N的边交错组成。且由于MN，存在H的一个分支，它是路P，起、止于M 边。因此 M=M E(P)及 N=N E(P)即为所求。定理6.3 设G为偶图，p，则存在G的p个互不相交的匹配使 E=M1 Mp。且,1 i p。,图论及其应用,15,6.2 排课表问题,证明：由定理6.1,E可划分为 个互不相交的匹配M1，M。因此，对p，G有p个互不相交的匹配M1，M，Mp。（令Mi=当i p）使E=M1 Mp。今对边数差 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-可着色的（k j）。,图论及其应用,17,6.3 顶点着色和色数,色数（chromatic number）(G)=k G为k-可着色的。G为k-色图(G)=k。例：设每一教师只开一门研究生课，每门课课时为一单元。问至少要多少单元才能排完所有课？解：作一图G，每一顶点对应一们课；两顶点相邻当且仅当有一研究生选修对应的两门课。由此，所需单元数(G)。例：设有一些药品存储在一仓库中，其中有些药品是不相容的，不能放在同一房间中，问至少应把仓库间隔成几个房间？G为临界的（crtical）(H)(G)H G G连通且满足(G-e)(G)e E(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.1 G为k-临界图 k-1。证明：反证，假设 k-1。取v V使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)=k G中至少有k个度 k-1 的顶点。证明：令H为G的k-临界子图。由定理8.1知 dH(v)(H)k-1 v V(H)。dG(v)dH(v)k-1 v V(H)。又因H为k-色的，必有|V(H)|k。#推论 对任一图G都有+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-complete prob：对任给图G及正整数k|V|，G是否为k-可着色的？从而，求任给图G的色数是个NP-hard prob.。,图论及其应用,23,6.3 顶点着色和色数,贪心（greedy）着色法：用色1，2，逐步（按某一 顶点排序）一个个顶点进行正常着色，每次选用尽可能小的颜色进行着色。例如，对任给图G，按任一顺序进行贪心着色，则每当尝试对某一顶点v着色时，其邻集N(v)中至多出现种色，因此总可从+1 种色中挑选一色着在v上。整个着色至多用了+1 种色，故G为(+1)-可着色的。从而得到推论的另一证明。显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图G的一个-着色为 C=（V1，V2，V）。按(V1，V2，V)的顺序任作一顶点排序（同一色集Vi内随意排序），按此顺序进行贪心着色，易见，一定恰好用了 个色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到关于着色的一个较好结果（如Brooks定理之证明）。下面是这方面的一些结果：,图论及其应用,24,6.3 顶点着色和色数,例。设图G 中度序列满足：d1 d，则 证明：不妨设顶点排序：v1，v 恰使d(vi)=d i i=1,2,.,。沿 进行贪心着色。不妨设某vk被着上了色。易见，它一定与前面-1个不同色的顶点相邻，因此 dk d(vk)-1。又，显然 k。min dk+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(k 2)u U V，而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 顶点着色和色数,.证明：若G 是简单图，则 2/(2-2)。8.1.2.证明：若G的任二奇圈都有公共顶点，则 5。.证明：设图G 中度序列满足d1 d，则.利用习题8.1.3 证明：(a)(b)(G)+(Gc)=+1。(c)推论8.1.1。.试证：(G)1+max(H)|H为G的导出子图。8.1.6.*设k-色图G上有这样一个正常着色（不一定为k-着色），其中每种色都至少分配给两个顶点。证明：G也有这样的k-着色。.证明：若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及 n 6 构造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)，使xiyj E 边割Xi,YjG=。利用习题5.2.6(b)证明H有完美匹配。由此构造G的n-着色。）,图论及其应用,28,8.1 色数习题（续）,8.1.15.求(Kn e)及(Kn e1-e2)，其中e、e1、e2 都是Kn 的边，且后两者互不相邻。8.1.16.任一4-可着色简单图G的边都有一红、兰2-边着色，使G中每一三角形都恰含一红边及二兰边（提示:令所用4色为0、1、2、3。对每边e=xy，令 色(e)=色(x)+色(y)(mod 2)）8.1.17 证明：奇圈数2 的图一定是3-可着色的。8.1.18 证明：。设e为简单图G的任一边，则(G e)=min(G),(Ge)。,图论及其应用,29,8.2 Brooks定理,图论及其应用,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，xnx1 E(G)而x1x2 E(G)下面我们由此来作V的一个排序：取xn-1 V x1,x2,xn 使xn-1N(xn)；取xn-2 V x1,x2,xn-1,使xn-2N(xn-1,xn)；由于G-x1，x2是连通的，上述步骤可一直进行到底，得V的一个排序：x1，x2，xn。其中每个xi（i i，相邻接。又，x1 与x2不相邻。于是，贪心着色法只用了 个色。#,图论及其应用,32,习题,8.2.1.证明Brooks定理等价于下述命题：若G是k-临界图（k 4），且不是完全图，则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满足要求（k 2），则由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年（Jurnals of Graph Theory,vol.3,p314）已证明该猜想不成立。,图论及其应用,35,8.4 围长和色数习题,8.3.1.证明：定理8.7中的图Gk是一k-临界图。8.3.2*(a)设G是围长至少为6的k-色图（k 2）。作一新图H如下：取k个新顶点集S及G的 个互不相交的拷贝，且建立G的拷贝与S的元子集之间的一一对应。再将G的每个拷贝的顶点和与它相应的S的元子集的元素用一匹配连接起来。证明：H的色数至少为k+1，其围长至少为6。(b)试证：对任 k 2，都存在围长为6的k-色图。（提示(a)：易证H的围长至少为6。若H为k-可着色的，则存在S 的元子集，其 元素都染有相同的颜色。再考察对应的G的拷贝得出矛盾。）,