《集合论与图论》第25讲1 第24讲图着色 ?1. k-(点,面,边)着色, k-(点,面,边)色图, 点色数χ(G), 面色数χ*(G), 边色数χ’(G) ?2. χ(G)上界, Brooks定理 ?3. 五色定理 ?4. Vizing定理 ?5. 色多项式f(G,k) 《集合论与图论》第25讲2 着色(coloring) ?着色: 给图的某类元素(点,边,面)中每个指 定1种颜色,使得相邻元素有不同颜色 ?用颜色集C给X中元素着色: f:X→C, ?x?y( x,y∈X∧x与y相邻→ f(x)≠f(y) ) 若|C|=k( 如C={1,2,…,k} ), 则称k-着色 ?(点)着色,边着色,面着色: X=V(无环),E,R ?相邻: V,有边相连,(x,y)∈E; E,有公共端 点, (x,y),(y,z); R,有公共边界 《集合论与图论》第25讲3 着色(例) 《集合论与图论》第25讲4 色数(chromatic number) ?k-色图: 可k-着色,但不可(k-1)-着色 ?色数: 着色所需最少颜色数 ?点色数χ(G), 边色数χ’(G), 面色数χ*(G) ?例: χ(G)=2, χ’(G)=4, χ*(G)=3 《集合论与图论》第25讲5 点色数性质 ?χ(G)=1 ? G是零图 ?χ(K n )=n ?χ(G)=2 ? G是非零图二部图 ?G可2-着色? G是二部图? G无奇圈 ?χ(C n )= 2, n偶数χ(W n )= 3, n奇数 3, n奇数4, n偶数 《集合论与图论》第25讲6 定理12.7 ?定理12.7: 对图G进行χ(G)-着色,设 V i ={v|v∈V(G)∧v着颜色i}, i=1,2,…, χ(G), 则Π={V 1 ,V 2 ,…,V χ(G) }是V(G)的划分. # ?定理12.7’:对图G进行χ(G)-着色,设 R={<u,v>| u,v∈V(G)∧u,v着同样颜色}, 则 R是V(G)上等价关系. # ?说明: V i 中的点构成“独立集” 《集合论与图论》第25讲7 χ(G)上界 ?定理12.5: χ(G) ≤Δ(G)+1 ?证明: ?v∈V(G), Γ G (v)={ u | (u,v)∈E(G) }, |Γ G (v)|≤Δ(G), 给Γ G (v)中顶点着色至多需 要Δ(G)种颜色, 所以至少还剩一种颜色可 用来给v着色. # ?定理12.6(Brooks): 若G连通非完全图K n (n≥3)非奇圈, 则χ(G) ≤Δ(G). # ?说明: n=1?G=K 1 , n=2: 连通?G=K 2 《集合论与图论》第25讲8 例12.1(Petersen图) ?例12.1: Petersen图χ=3. ?解1: 由Brooks定理, χ≤Δ=3. 又图中有奇 圈, χ≥3. 所以χ=3. # ?解2: 存在如下3-着色, χ≤Δ=3. 又图中有 奇圈, χ≥3. 所以χ=3. # ?思考题: 至少有3点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的) 《集合论与图论》第25讲9 地图 ?地图: 连通无桥平面图的平面嵌入及其所 有的面称为(平面)地图 ?国家: 平面地图的面 ?相邻: 两个国家的公共边界至少有一条公 共边 ?k-面着色, k-色地图, 面色数χ*(G) 《集合论与图论》第25讲10 面着色与对偶图点着色 ?定理12.13: 地图G可k-面着色?对偶图 G*可k-着色. # ?定理12.14: 连通无环平面图G可k-面着色 ?对偶图G*可k-着色. # ?研究平面图面着色?研究平面图点着色 《集合论与图论》第25讲11 平面图着色 ?定理12.15: 任何平面图都可6-着色 ?证明: (归纳法) (1) n≤7: 结论为真. (2) 设n=k(≥7)时结论为真. n=k+1时, ?v∈V(G), d(v)≤5. 令G 1 =G-v, 对G 1 用归 纳假设, G 1 可6-着色. 模仿G 1 对G着色, 与 v相邻的点不超过5个, 至少剩1种颜色给v 着色,所以G可6-着色. # 《集合论与图论》第25讲12 五色定理 ?定理12.16(Heawood,1890): 任何平面图 都可5-着色 ?证明: (归纳法) (1) n≤5: 结论为真. (2) 设n=k(≥5)时结论为真. n=k+1时, ?v∈V(G), d(v)≤5. 令G 1 =G-v, 对G 1 用归 纳假设, G 1 可5-着色. 模仿G 1 对G着色, 当 d(v)<5, 或d(v)=5但与v相邻的点用了少于 5种颜色时, 至少剩1种颜色给v着色. 《集合论与图论》第25讲13 五色定理(续) ? 《集合论与图论》第25讲14 五色定理(续) ?证明: (续) 当d(v)=5且与v相邻的点用了5 种颜色时, 设v i 与v相邻且着颜色i, i=1, 2,…, 5. 根据Jordan定理,下面2种路径不 能同时存在: 从v 1 到v 3 只有{1,3}这2种颜 色的路径, 从v 2 到v 4 只有{2,4}这2种颜色 的路径. 不妨设在只有{1,3}这2种颜色的 顶点的导出子图中, v 1 与v 3 是在不同的连 通分支中, 于是把v 1 所在分支里1与3颜色 互换, 然后把颜色1给v. # 《集合论与图论》第25讲15 边着色 ?边色数: χ’(G) ?定理12.17(Vizing): G是简单图,则 Δ(G) ≤χ’(G) ≤Δ(G)+1. # ?G=<V 1 ,V 2 ,E>是二部图, 则χ’(G)=Δ(G) ?n>1时, χ’(K n )= n, n为奇数 n-1, n为偶数 《集合论与图论》第25讲16 例12.5 ?G=<V 1 ,V 2 ,E>是二部图, 则χ’(G)=Δ(G) ?证明: (归纳法) (1) m=0,1: 结论为真. (2) 设m=k(≥1)时结论为真. m=k+1时, ?e=(u,v)∈E(G). 令G 1 =G-e, Δ(G 1 )≤Δ(G) =Δ, 对G 1 用归纳假设, G 1 可Δ-边着色. 模 仿G 1 对G边着色, 当存在颜色α既不出现 在u也不出现在v时, 用颜色α给e着色. 《集合论与图论》第25讲17 例12.5(续) u v u v u v ? ? u v u v u v e e u v ? 《集合论与图论》第25讲18 例12.5(续) ?证明(续): 设颜色β出现在u而不出现在v, 颜色γ出现在v而不出现在u. 则不存在这 样的路径: 从v到u只有{β,γ}这2种颜色的 路径, 即在只有{β,γ}这2种颜色的边的导 出子图中, v与u是在不同的连通分支中. 于是把v所在分支里β与γ颜色互换, 然后 把颜色γ给e=(u,v). # 《集合论与图论》第25讲19 例12.6 ?n>1时, χ’(K n )= n, n为奇数 n-1, n为偶数 ?证明: (1) n为奇数时, χ’(K n )=n. 每边关联 2个不同端点, 同色边没有公共端点, 同色 边至多有(n-1)/2条, 至少需要n种颜色, χ’(K n )≥n. 又存在n-边着色, χ’(K n )≤n. 所以 χ’(K n )=n. 《集合论与图论》第25讲20 例12.6(续) ?证明: (续) (2) n为偶数时, χ’(K n )=n-1. 每 边关联2个不同端点, 同色边没有公共端 点, 同色边至多有n/2条, 至少需要n-1种 颜色, χ’(K n )≥n-1. 又存在(n-1)-边着色, χ’(K n )≤n-1. 所以χ’(K n )=n-1. # 《集合论与图论》第25讲21 例12.7 ?某一天内有n个教师给m个班上课.每个教 师在同课时只能给一个班上课. (1) 这一天内至少排多少节课? (2) 不增加节数情况下至少需要几个教室? (3) 若n=4,m=5. 教师是t 1 ,t 2 ,t 3 ,t 4 , 班是c 1 , c 2 ,c 3 ,c 4 ,c 5 . 已知t 1 给c 1 ,c 2 ,c 3 上2节,1节,1 节课, t 2 给c 2 ,c 3 各上1节课, t 3 给c 2 ,c 3 ,c 4 各 上1节课, t 4 给c 4 ,c 5 上1节,2节课. 求最省教 室的课表. 《集合论与图论》第25讲22 例12.7(解) ?解: 令G=<T,C,E>, T={t 1 ,t 2 ,…,t m }, C={c 1 ,c 2 ,…,c n }, E={(t i ,c j )| t i 给c j 上一节课}. 给G进行边着色, 同色边代表的教学可以 同时进行, 所以颜色数就是节数, 同色边 数就是教室数. (1) k=χ’(G)=Δ(G)时, 节数最少. (2) min max {k 1 ,k 2 ,…,k Δ }, 教室数最少. 其 中k i 是着颜色i的边数. (“平衡”着色) 《集合论与图论》第25讲23 例12.7(解,续) ?解: (续) (3) 已知条件得出下图G, T={t 1 ,t 2 ,…,t 4 }, C={c 1 ,c 2 ,…,c 5 }. Δ(G)=4, 节数最少是4. min max {k 1 ,k 2 ,…,k 4 }=3, 教室数最少是3. 课表如下. # t 1 t 2 t 3 t 4 c 1 c 2 c 3 c 4 c 5 《集合论与图论》第25讲24 例12.7(解,续) c 4 c 3 --c 1 2 c 5 c 2 --c 3 4 c 5 --c 3 c 2 3 --c 4 c 2 c 1 1 t 4 t 3 t 2 t 1 节 《集合论与图论》第25讲25 边着色 ?设无环图G=<V,E>,给G进行k-边着 色,k≥χ’(G). 令 R={ (e i ,e j ) | e i 与e j 着同色} 则R是E上等价关系, 商集合 E/R={E 1 ,E 2 ,…,E k } 是E的划分, 划分块中元素着同色 ?说明: 同色边构成“边独立集”, 或“匹配” 《集合论与图论》第25讲26 例 《集合论与图论》第25讲27 色多项式 ?设G是n阶无向图. 说两个k-着色不同, 是 指两个k-着色中至少有1个顶点颜色不同 ?f(G,k)=G的不同k-着色方式的总数 ?χ(G)=min{ k | f(G,k)>0 }; f(G,k)是n次多 项式(色多项式); 各项系数的符号是正负 交替的; k n 项系数是1; k n-1 项系数是-m; k 0 项系数是0; 系数非0的项的最低次幂是k p , p是连通分支数; 若G的连通分支是 G 1 ,G 2 ,…,G p , 则f(G,k)=Π p i=1 f(G i ,k); 《集合论与图论》第25讲28 求色多项式 ?递推公式: f(G,k)=f(G∪e,k)+f(G\e,k), e?E f(G,k)=f(G-e,k)-f(G\e,k), e∈E ?零图: f(N n ,k)=k n ?完全图: f(K n ,k)=k n =k(k-1)…(k-n+1) ?树: f(T,k)=k(k-1) n-1 ?圈: f(C n ,k)=(k-1) n +(-1) n (k-1) 《集合论与图论》第25讲29 例12.2 ?例12.2: 求f(K n ,6), n≥1. ?解: f(K 1 ,6)=6 1 =6, f(K 2 ,6)=6 2 =6×5=30, f(K 3 ,6)=6 3 =6×5×4=120, f(K 4 ,6)=6 4 =6×5×4×3=360, f(K 5 ,6)=6 5 =6×5×4×3×2=720, f(K 6 ,6)=6 6 =6×5×4×3×2×1=720, f(K 7 ,6)=6 7 =6×5×4×3×2×1×0 =0, … # ?注意: f(K n ,k)=f(K n-1 ,k)(k-n+1), n≥2 《集合论与图论》第25讲30 色多项式递推公式 ?定理12.9: (1) f(G,k)=f(G∪e,k)+f(G\e,k),e?E(G) (2) f(G,k)=f(G-e,k)-f(G\e,k), e∈E(G) 证明: (1) 设e=(u,v). u,v着不同颜色的着色 总数是f(G∪e,k), u,v着相同颜色的着色总 数是f(G\e,k). (2) 对G-e利用(1): e?E(G-e), (G-e)∪e=G, f(G-e,k)=f(G,k)+f(G\e,k). # 《集合论与图论》第25讲31 推论 ?推论: f(G,k)=f(K n1 ,k)+f(K n2 ,k)+…+f(K nr ,k), χ(G)=min{ n 1 ,n 2 ,…,n r } ?证明: 反复利用递推公式(1), 以及 χ(G)=min{ k | f(G,k)>0 }, χ(K n )=n. # ?例12.3: 求下图G的色多项式. 《集合论与图论》第25讲32 例12.3(解) ?解: f(G,k)=f(K 5 ,k)+3f(K 4 ,k)+f(K 3 ,k) =k 5 +3k 4 +k 3 =k 5 -7k 4 +18k 3 -20k 2 +8k 1 . χ(G)=min{ 5,4,3 }=3. f(G,3)=6. # 2 3 《集合论与图论》第25讲33 定理12.10 ?定理12.10: 设V 1 是G的点割集, 且G[V 1 ]是 完全图, G-V 1 有p(≥2)个连通分支G 1 , G 2 ,…,G p . 则 f(G,k) = Π p i=1 f(H i ,k) / f(G[V 1 ],k) p-1 ; 其中H i =G[V 1 ∪V(G i )]. 《集合论与图论》第25讲34 定理12.10(证明) ?证明: f(G,k) = f(G[V 1 ],k)?Π p i=1 (f(H i ,k)/f(G[V 1 ],k)) = Π p i=1 f(H i ,k) / f(G[V 1 ],k) p-1 . # 《集合论与图论》第25讲35 定理12.11 ?定理12.11: T是n阶树?f(T,k)=k(k-1) n-1 ?证明: (?) (归纳法) 对m归纳. 设删除分支 点u(割点)后有t个分支T i , 则由定理12.10: f(T,k) = Π t i=1 f(G[T i ∪{u}],k) / f(G[{u}],k) t-1 =Π t i=1 k(k-1) ni / k t-1 =k t (k-1) Σni /k t-1 =k(k-1) n-1 . (?) f(T,k) = k(k-1) n-1 = k n -(n-1)k n + …+(-1) n-1 k, m=n-1,p=1(连通),是树. # 《集合论与图论》第25讲36 定理12.12 ?定理12.12: f(C n ,k)=(k-1) n +(-1) n (k-1) ?证明: (归纳法)对n归纳. 任取1边e, C n -e 是n阶树, C n \e是圈C n-1 . 由递推公式 f(G,k)=f(G-e,k)-f(G\e,k) =k(k-1) n-1 -((k-1) n-1 +(-1) n-1 (k-1)) =(k-1) n +(-1) n (k-1). # 《集合论与图论》第25讲37 例12.4 ?例12.4: 有5门选修课c 1 ,c 2 ,…,c 5 , 已知c 1 与c 2 , c 2 与c 3 , c 3 与c 4 , c 4 与c 5 , c 2 与c 4 都有 学生同时选它们. 每天每个学生至多只能 参加1门课的考试, 问在安排天数最少的 条件下,至多有多少安排方案? ?解: 令G=<C,E>,C={c 1 ,c 2 ,…,c 5 }, E={ (c i ,c j ) | 有学生同时选c i 和c j } 《集合论与图论》第25讲38 例12.4(续) ?解: (续) 给G进行k-着色, 同色点代表可以 同一天考的课程, 颜色数就是天数, 最少 需要k=χ(G)=3天. G的色多项式 f(G,k)=k 5 -5k 4 +9k 3 -7k 2 +2k, 所以至多有 f(G,3)=24种安排方案. # c 1 c 2 c 5 c 4 c 3 《集合论与图论》第25讲39 总结 ?点色数χ(G), 面色数χ*(G), 边色数χ’(G) ?χ(G)上界: χ≤Δ+1 ?Brooks定理:连通非完全(n≥3)非奇圈:χ≤Δ. ?五色定理: χ* ≤ 5 ?Vizing定理: 简单图: Δ≤χ’ ≤Δ+1. ?色多项式f(G,k) 《集合论与图论》第25讲40 作业(#20) ?补充题: 求下列图的点色数 ?p315, 习题十二, 11, 12, 14