《集合论与图论》第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