《图论》第6章-图的着色2.ppt

1图的着色包括对边、顶点和平面区域的着色。本章主要讨论简单图的顶点着色。例 6种化学制品，某些不能放在同一仓库。用矩阵表示,例如(a,b)=1表示 a 和 b 不能放在同一仓库。问：最少需要几个仓库？第六章第六章 图的着色图的着色第一页，编辑于星期六：八点 一分。2解 以该矩阵为邻接矩阵构造图如上所示。给图的顶点染色使得相邻点具有不同颜色，最少需要3种颜色。第六章第六章 图的着色图的着色acbdef第二页，编辑于星期六：八点 一分。3着色 图 G=(V,E)的一个 k 顶点着色指用 k 种颜色对 G 的各顶点的一种分配方案。若着色使得相邻顶点的颜色都不同，则称该着色正常，或称 G 存在一个正常的 k 顶点着色（或称一个 k 着色）。此时称 G 为 k-可着色的。色数 使 G=(V,E)k-可着色的最小 k 值称为 G 的色数，记为(G)。若(G)=k，称 G 为 k 色图。6.1 色数第三页，编辑于星期六：八点 一分。4例 三色图6.1 色数第四页，编辑于星期六：八点 一分。5特殊图的色数特殊图的色数 零图：(G)=1 完全图 Kn：(G)=n G 是一条回路：(G)=2 若|V|是偶数 (G)=3 若|V|是奇数 G 是一棵非平凡树：(G)=2 (G)=2的充要条件是:(a)|E|1；(b)G 中不存在边数为奇数的回路。（此时 G 为二部图）若 G1、G2为 G 的两个连通分支，则 (G)=max(G1),(G2)6.1 色数第五页，编辑于星期六：八点 一分。6 (G)=2的充要条件是:(a)|E|1；(b)G 中不存在边数为奇数的回路。（此时 G 为二部图）证明 必要性显然。充分性：由(a)|E|1知(G)2。对 G 中的某一连通分支，找到其一棵生成树，对顶点做二染色。加上任意一条余树枝，得到对应的唯一回路。由(b)知该回路长度为偶数，该余树枝两个端点染的是不同颜色，添加该余树枝后仍然可以保持原来的二染色。加上所有余树枝，得到图 G，二染色仍得到保持，即(G)=2。6.1 色数第六页，编辑于星期六：八点 一分。7临界图 G=(V,E)，若对 G 的任一真子图 H 均有(H)(G)，则称 G 为一个临界图。k 色临界图称为 k-临界图。性质 任何 k 色图通过对边的反复删减测试最后可以得到其 k-临界子图。临界图是连通图。证 设 G1、G2为临界图 G 的两个连通分支，则(G)=max(G1),(G2)。不妨设(G)=(G1)，而G1为 G 的真子图，与临界图的定义矛盾。6.1 色数第七页，编辑于星期六：八点 一分。8定理6-1-1 k-临界图 G=(V,E),=mindeg(vi)|viV,则 k-1。证明 反证法：设 G 是一个 k-临界图且 k-1。又设v0V，deg(v0)=。由 k-临界图的定义，Gv0 是(k1)可着色的，在一种 k1着色方案下，Gv0 的顶点可按照颜色划分成 V1,V2,Vk-1 共 k1块，块 Vi 中的顶点被涂以颜色 ci。由于deg(v0)k1，v0 至少与其中一块 Vj 不邻接即与 Vj 中的任何顶点不邻接。此时可将 v0 涂以颜色 cj，从而获得对 G 的一种 k1着色方案，与 G 的色数是 k 矛盾。6.1 色数第八页，编辑于星期六：八点 一分。9推论1 k 色图至少有 k 个度不小于 k-1 的顶点。证明 设 k 色图 G 的 k-临界子图为 G，由定理，G 的最小度 k-1，故 G 的最小度 k-1，即 G的任何顶点的度不小于 k-1。又 G 为 k 色图，其中至少有 k 个顶点。6.1 色数第九页，编辑于星期六：八点 一分。10推论2 对 G=(V,E)，=maxdeg(vi)|viV，有 (G)+1。证明 设(G)=k，由推论1，有 vV，使得deg(v)k-1又：deg(v)故：k-1 或 (G)-1 即：(G)+1推论2给出了色数的一个上限，但很不精确。例例 二部图可二染色，但是 可以相当大。6.1 色数第十页，编辑于星期六：八点 一分。11Hajs猜想 若 G 是 k 色图,则 G 包含 Kk 的一个同胚图。(1961)四色猜想 任何平面图都是 4-可着色的。由于存在着不可3-着色的平面图 K4，4色问题若可证明，将是平面图色数问题的最佳结果。6.1 色数第十一页，编辑于星期六：八点 一分。12定理6-1-2 如果平面图 G 有 Hamilton 回路，则 G 的域域是4-可着色的。证明 平面图 G 的一条 Hamilton 回路将 G 的域分割成两部分：被封闭的 H-回路包围部分和在 H-回路之外部分。每一部分中只能出现两域相邻的情况，否则同一部分内三个域的交点将不在H-回路上，引起矛盾。将两部分的域分别以2着色，得到G 的一种4着色方案。6.1 色数第十二页，编辑于星期六：八点 一分。13五色定理(1890,Heaword)任何简单平面图都是 5-可着色的。证明 设简单平面图 G=(V,E)，对 n=|V|作归纳。n 5时容易讨论结论成立。设 n=k1时，结论成立。当 n=k 时，由定理5-1-8简单平面图 G 至少有一个顶点的度小于6。故可设 v0V，deg(v0)5。设 G=Gv0，由归纳假设，G 是5-可着色的。给 G 固定一种5-着色方案,再将 v0 加回 G 得到 G，在此情况下讨论 v0 的着色。(1)若 deg(v0)4，则 v0 最多邻接4种颜色的顶点，给 v0 着以第5 种颜色得到 G 的一种5-着色方案。(2)否则 deg(v0)=5，设 v0 的邻接点按逆时针排列为 v1,v2,v3,v4,v5,如图所示。6.1 色数第十三页，编辑于星期六：八点 一分。14 若 v1 v5 的着色数 4，则 v0 最多邻接4种颜色的顶点，给 v0 着以第5 种颜色得到 G 的一种5-着色方案。否则 v1 v5 分别被着以颜色 c1c5，则V-v0按着色可被划分成V13（着色 c1或 c3的顶点）、V24（着色 c2或 c4的顶点）和V5（着色c5的顶点）。设G13和G24分别是V13和V24在G 的导出子图。v0v2v1v5v4v3 (a)若 v1 和 v3 在 G13中不连通，将 G13中 v1 所在连通分支所有顶点颜色对换，得到 G 的另外一种5-着色方案。此时 v1 和 v3 都着色 c3，即 v1 v5 的着色数=4。由得到 G 的一种5-着色方案。6.1 色数第十四页，编辑于星期六：八点 一分。15(b)若 v1 和 v3 在 G13中有连通路径 P13，在 G 中 v2 和 v4 连通的任一路径 P24必和 P13相交（平面图形的 Jordan 原理），设交点为 u，则 u 着色 c1或 c3，即 uV24，在导出 G24 时 P24不能被导出，故 v2 和 v4 在 G24中不连通。对 v2 和 v4 作类似(a)的讨论，可以得到 G 的一种5-着色方案。结论：综合上述讨论，n=k 时结论仍然成立。由归纳原理，定理得证。v0v2v1v5v4v3P13P24u6.1 色数第十五页，编辑于星期六：八点 一分。16定理6-1-3 G=(V,E)为简单图，vi,vj 为其中不相邻顶点。Gij+为在 G 中添加边(vi,vj)得到的图，Gijo 为在 G 中合并 vi,vj，其他顶点与其关系不变，并合并多重边（称为收缩 vi,vj）得到的图。则有：(G)=min(Gij+),(Gijo)证明 对 G 的着色方案可以划分为令 vi,vj 得到不同颜色的和令 vi,vj 得到相同颜色的两类，前者与 Gij+的着色方案一致，后者与 Gijo 的着色方案一致。由色数的定义得到结论。6.1 色数第十六页，编辑于星期六：八点 一分。17例 如图，求(G)。6.1 色数第十七页，编辑于星期六：八点 一分。18 (G)=min(K5),(K4),(K3)=(K3)=36.1 色数 K5 K4 K4 K3第十八页，编辑于星期六：八点 一分。19定义 PG(k)为对给定的图 G=(V,E)，以 k 种颜色进行正常着色的方案数目。当 k0（存在4-着色方案）令一个顶点着不同颜色的方案视为不同方案。如PK3(3)=66.2 色数多项式第十九页，编辑于星期六：八点 一分。20PK3(3)=6abcabcabcabcabcabc6.2 色数多项式第二十页，编辑于星期六：八点 一分。21若干特殊图的 PG(k)1)零图：G=(V,E)，n=|V|，|E|=0，PG(k)=kn2)树：根节点在 k 种颜色中任取，非根节点选取与其父亲节点不同的颜色。PG(k)=k(k-1)n-13)完全图：PG(k)=k(k-1)(k-2)(k-n+1)4)非连通图：设图 G 由不连通的 G1和 G2构成，则由乘法原理：PG(k)=PG1(k)PG2(k)6.2 色数多项式第二十一页，编辑于星期六：八点 一分。22定理6-2-1 设简单图 G，Gij+和Gijo 分别如前所述，并分别记 P1(k)和 P2(k)为 Gij+和 Gijo 的 k 染色方案数，则有 PG(k)=P1(k)+P2(k)。证明 参考定理6-1-3的证明，结合色数多项式的定义得到。6.2 色数多项式第二十二页，编辑于星期六：八点 一分。23推论1 设简单图 G=(V,E)，n=|V|，m=|E|，k (G)，则 PG(k)是 k 的整系数 n 次多项式，且：首项为 kn；次项为-mkn-1；常数项为0；各项系数的符号正-负交替。证明 对m归纳。(1)m=0时，G 为零图，PG(k)=kn。m=1时，若 n=2，则 G 为 K2，PG(k)=k(k1)=k2k。若 n2，则 G 除一个 K2 外其它为孤立点：PG(k)=k(k1)kn-2=knkn-1。6.2 色数多项式第二十三页，编辑于星期六：八点 一分。24 (2)设 m t 时结论成立，记为：6.2 色数多项式 (3)当 m=t 时，设 e=(vi,vj)E为 G 中任意一边，从 G 中去除e，得到图 G，则有 G=Gij+。由定理6-2-1知PG(k)=PGij+(k)+PGijo(k)故 PG(k)=PGij+(k)=PG(k)PGijo(k)。G 的顶点数为 n，边数为 m=t1 t，由归纳假设有：第二十四页，编辑于星期六：八点 一分。25 Gijo 的的顶点数为 n1，边数 mmt，由归纳假设有：-并合并化简得：可见 m=t 时结论成立。由归纳原理，原题得证。色数多项式 推论1证明了函数 PG(k)具有多项式形式，称之为图 G 的色数多项式。6.2 色数多项式第二十五页，编辑于星期六：八点 一分。26推论2 图 G=(V,E)是树当且仅当 PG(k)=k(k1)n-1，n=|V|。证明 必要性显然（见P.21）。充分性：(1)先证此时 G 连通。若 G 不连通，设分为 G1,G2 两部分，则：PG(k)=PG1(k)PG2(k)。由推论1，PG1(k)和 PG2(k)均无常数项,则其乘积中必无一次项。但 PG(k)=k(k1)n-1中有一次项 k，矛盾。(2)PG(k)=k(k1)n-1中=kn(n1)kn-1+=由推论1，m=n 1，这里 m=|E|。结合(1)(2)，G 是一棵树。6.2 色数多项式第二十六页，编辑于星期六：八点 一分。27减边法：求给定图 G 的色数多项式 原理：由定理6-2-1，P1(k)=PG(k)P2(k)，其中 PG(k)和 P2(k)对应的 G 和 Gijo 都是边数比 P1(k)对应的 Gij+少的图，将它们视为分别由Gij+减边得到。在图 G 中任取一边 e；在图 G 中去掉 e，得新图 G1；在图 G 中收缩 e 的两端点，得新图 G2，由上述有 PG(k)=PG1(k)PG2(k)继续分解 G1和 G2，直到最后全部为零图。利用 n 阶零图的 P(k)=kn 构造图 G 的色数多项式。6.2 色数多项式第二十七页，编辑于星期六：八点 一分。28例 如图，求其色数多项式。6.2 色数多项式第二十八页，编辑于星期六：八点 一分。296.2 色数多项式PG(k)=k43k3+3k2k第二十九页，编辑于星期六：八点 一分。30分析 设图 G=(V,E)，n=|V|，m=|E|，分解深度 d=m，二元分解树结点数=2d1=2m1。减边法比较适合于求稀疏图的色数多项式6.2 色数多项式第三十页，编辑于星期六：八点 一分。31加边法：求给定图 G 的色数多项式 原理：由定理6-2-1，PG(k)=P1(k)+P2(k)P1(k)和 P2(k)对应图 Gij+和 Gijo。在图 G 中任取两个不相邻顶点 u,v；在图 G 中加上(u,v)，得新图G1，在图 G 中收缩(u,v)，得新图 G2，由上述讨论有 PG(k)=PG1(k)+PG2(k)继续分解 G1和 G2，直到最后全部为完全图。利用 n 阶完全图的 P(k)=k(k1)(k2)(kn+1)构造图 G 的色数多项式。6.2 色数多项式第三十一页，编辑于星期六：八点 一分。32例 如图，求其色数多项式。6.2 色数多项式第三十二页，编辑于星期六：八点 一分。33PG(k)=PK4(k)+2PK3(k)+PK2(k)=k(k1)(k2)(k3)+2k(k1)(k2)+k(k1)=k44k3+6k23k6.2 色数多项式第三十三页，编辑于星期六：八点 一分。346.2 色数多项式分析 设图 G=(V,E)，n=|V|，m=|E|，分解深度即 G 的补图的边数。二元分解树结点数=2d1。加边法比较适合于求稠密图的色数多项式。第三十四页，编辑于星期六：八点 一分。35进一步的讨论判断一个多项式为某一个图的色数多项式的有效方法的研究。具有相同色数多项式的图的共性的研究。同构的图具有相同的色多项式，但其逆不真。例如：图 G 和 G不是同构的，但有相同的色多项式：PG(k)=PG(k)=k2(k1)2 GG6.2 色数多项式第三十五页，编辑于星期六：八点 一分。36独立集 图 G=(V,E)，BV，若 B 中任意两个顶点都不相邻，则称 B 为 G 的一个点独立集(独立集)。B 为 G 的一个独立集 B V(u)(v)(u,vB(u,v)E)例独立集：b,d，b,f，a,c，b,d,f ，acbdef6.3 独立集、支配集和覆盖集第三十六页，编辑于星期六：八点 一分。37极大独立集 B 为 G 的一个极大独立集 B 为 G 的一个独立集(u)(uVBBu不是 G 的独立集)独立数 设 G 的所有独立集为 B1、B2、Bk，记 称为 G 的独立数。最大独立集 对 G 的一个独立集 Bi，若有|Bi|=0，则称 Bi 为 G 的一个最大独立集。G 的一个最大独立集是 G 的一个极大独立集。独立数是唯一的，但最大独立集不一定唯一。6.3 独立集、支配集和覆盖集第三十七页，编辑于星期六：八点 一分。38例对图 G=(V,E)的一次 k 正常着色，相当于将 V 划分成为 k 个不相交的点独立集。独立集：b,d,b,f,a,c,b,d,f,极大独立集：a,c,b,e,b,d,f 独立数：0 =3最大独立集：b,d,f acbdef6.3 独立集、支配集和覆盖集第三十八页，编辑于星期六：八点 一分。39支配集 图 G=(V,E)，DV，若 G 的任何顶点或属于D，或至少与 D 中一点邻接，则称 D 为 G 的一个支配集。D 为 G 的一个支配集 D V(u)(uV uD(v)(vD(u,v)E)例支配集：a,c,b,e,b,d,f,a,b,c,a,b,c,d,e,f,acbdef6.3 独立集、支配集和覆盖集第三十九页，编辑于星期六：八点 一分。40极小支配集 D 为 G 的一个极小支配集D 为 G 的一个支配集(u)(uDDu不是 G 的支配集)支配数 设 G 的所有支配集为 D1、D2、Dk，记 称之为 G 的支配数。最小支配集 对 G 的一个支配集 Di，若有|Di|=0，则称 Di 为 G 的一个最小支配集。G 的一个最小支配集是 G 的一个极小支配集。支配数是唯一的，但最小支配集不一定唯一。6.3 独立集、支配集和覆盖集第四十页，编辑于星期六：八点 一分。41例支配集：a,c,b,e,c,f,b,d,f,a,b,c,a,b,c,d,e,f,极小支配集：a,c,b,e,c,f,b,d,f 支配数：0 =2最小支配集：a,c,b,e,c,facbdef6.3 独立集、支配集和覆盖集第四十一页，编辑于星期六：八点 一分。42定理6-3-1 设 G=(V,E)无孤立点，则：(1)G 的一个极大独立集必也是 G 的一个极小支配集；(2)0 0；(3)若 S 为 G 的一个独立集，则 VS 为 G 的一个支配集；(4)若 G 为简单图，n=|V|，则有 0+0 n。证明6.3 独立集、支配集和覆盖集第四十二页，编辑于星期六：八点 一分。43证明 (1)设 SV为 G 的一个极大独立集。w若 S 不是 G 的支配集，则有 uVS，u 与 S 中的所有顶点都不邻接。此时 Su为 G 的一个独立集,与 S 是 G 的一个极大独立集矛盾。故 S 是 G 的一个支配集。w若 S 是 G 的一个支配集但不是极小支配集，则有 uS，使得 Su 为 G 的一个支配集。由于 uSu，则必有 vSu，使得 u,v 在 G 中邻接。此时 u,vS，且(u,v)E，与 S 是 G 的一个独立集矛盾。w反之不一定。如上例的 c,f 是 G 的一个极小支配集，但不是独立集。6.3 独立集、支配集和覆盖集第四十三页，编辑于星期六：八点 一分。44证明 续 (2)设 SV 为 G 的一个最大独立集，则有|S|=0。又由(1)，此时 S 亦为 G 的一个支配集，则有 0|S|。故有0 0 。(3)设 SV 为 G 的一个独立集。对任意的 uVS，即 uS，由于 G 中无孤立点，故必有v，使得(u,v)E。又 S 为独立集，故必须 vS，即 vVS。因此 S 中的任何顶点必与 VS 中的一点邻接。由定义知 VS 为 G 的一个支配集。（反之不一定。）(4)设 SV 为 G 的一个最大独立集，则有|S|=0。由(3)知 VS 为 G 的一个支配集,0|VS|=n0。故 0+0 n。讨论 当 G 有孤立点时的讨论。6.3 独立集、支配集和覆盖集第四十四页，编辑于星期六：八点 一分。45点覆盖 图 G=(V,E)，CV，若 G 的任何一条边都至少与 C 中一个顶点关联，则称 C 为 G 的一个点覆盖集（点覆盖）。C 为 G 的一个点覆盖 CV(e)(e=(u,v)E uCvC)例acbdef点覆盖：a,b,c,e,a,b,c,d,e,a,c,e,6.3 独立集、支配集和覆盖集第四十五页，编辑于星期六：八点 一分。46极小点覆盖 C 是 G 的一个极小点覆盖 C 为 G 的一个点覆盖(u)(uCCu不是 G 的点覆盖)点覆盖数 设 G 的所有点覆盖为C1、C2、Ck，记 称之为 G 的点覆盖数。最小点覆盖 对 G 的一个点覆盖 Ci，若有|Ci|=0，则称 Ci 为 G 的一个最小点覆盖。G 的一个最小点覆盖是 G 的一个极小点覆盖。点覆盖数是唯一的，但最小点覆盖不一定唯一。6.3 独立集、支配集和覆盖集第四十六页，编辑于星期六：八点 一分。47例点覆盖：a,b,c,d,e,a,b,c,e,a,c,e,极小点覆盖：a,c,e,b,d,e,f,a,c,d,f 点覆盖数：0 =3最小点覆盖：a,c,eacbdef6.3 独立集、支配集和覆盖集第四十七页，编辑于星期六：八点 一分。48定理6-3-2 设图 G=(V,E)无孤立点，CV，则：C 为G 的一个点覆盖 VC 为 G 的一个独立集。证明 设 C 为 G 的一个点覆盖。若 VC 不独立，则有 u,vVC且(u,v)E，即有 u,vC 且(u,v)E，与 C 为 G 的一个点覆盖矛盾。设 VC 为 G 的一个独立集。对任意的 u,vV 且(u,v)E，欲证 uC 或 vC。作反证：若此时 uC 且 vC，即 u,vVC 且(u,v)E，与 VC 为 G 的一个独立集矛盾。讨论 比较定理6-3-2和定理6-3-1之(3)。6.3 独立集、支配集和覆盖集第四十八页，编辑于星期六：八点 一分。49推论1 G 如上所述，CV，则：C 为 G 的一个极小点覆盖 VC 是 G 的一个极大独立集。推论2 G 如上所述，n=|V|，则 0+0 =n。讨论 上述推论的证明。6.3 独立集、支配集和覆盖集第四十九页，编辑于星期六：八点 一分。