《图论》第6章-图的着色.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)=26.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-16.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(k-1)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(k-1)n-1中有一次项 k，矛盾 (2) PG(k)=k(k-1)n-1中= kn- (n-1)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 都是边数比 Gij+ 少的图. 在图 G 中任取一边 e； 在图 G 中去掉 e，得新图 G1； 在图 G 中收缩 e 的两端点，得新图 G2，由上述。