北京大学：《离散数学》系列课程之一《集合论与图论》第24讲 图着色

第24讲图着色 1.k(点,面边)着色,k(点面边)色图, 点色数x(G,面色数x*(G,边色数x(G) 2.x(G)上界, Brooks定理 3.五色定理 4. iZing定理 5.色多项式fG.k) 《集合论与图论》第25讲

《集合论与图论》第25讲 1 第24讲 图着色 1. k-(点,面,边)着色, k-(点,面,边)色图, 点色数χ(G), 面色数χ*(G), 边色数χ’(G) 2. χ(G)上界, Brooks定理 3. 五色定理 4. Vizing定理 5. 色多项式f(G,k)

着色(ong 着色:给图的某类元素(点边,面)中每个指 定1种颜色,使得相邻元素有不同颜色 秦用颜色集C给X中元素着色:fX→>C, Xy(Xy∈x∧x与y相邻→fx)f(y)) 若C=k(如C={1,2,k),则称k-着色 春(点)着色,边着色面着色:X=V无环,ER 相邻:V,有边相连xy)∈E;E,有公共端 点,(Xy),yz);R有公共边界 《集合论与图论》第25讲

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

《集合论与图论》第25讲 3 着色(例)

色数( hromatic number) k色图:可k-着色,但不可(k1)着色 色数:着色所需最少颜色数 点色数x(G,边色数(G,面色数x*(G) 秦例:x(G)=2,x(G=4,x(G)=3 《集合论与图论》第25併

《集合论与图论》第25讲 4 色数(chromatic number) k-色图: 可k-着色,但不可(k-1)-着色 色数: 着色所需最少颜色数 点色数χ(G), 边色数χ’(G), 面色数χ*(G) 例: χ(G)=2, χ’(G)=4, χ*(G)=3

点色数性质 x(G=1台G是零图 n (G)=2÷G是非零图二部图 秦G可2着色→G是二部图G无奇圈 (C=2,n偶数xN)=3,n奇数 3,n奇数 4,n偶数 《集合论与图论》第25讲

《集合论与图论》第25讲 5 点色数性质 χ(G)=1 ⇔ G是零图 χ(Kn)=n χ(G)=2 ⇔ G是非零图二部图 G可2-着色 ⇔ G是二部图 ⇔ G无奇圈 χ(Cn)= 2, n偶数 χ(Wn)= 3, n奇数 3, n奇数 4, n偶数

定理127 定理127:对图G进行X(G)-着色设 v= LVVEV(G八∨着颜色门,=1,2,…,(G), 则∏=V12…4(是的划分# 定理127:对图G进行X(G)-着色设 R={4u>|ueV(G)八u,着同样颜色},则 R是VG)上等价关系,# 鲁说明:V中的点构成独立集” 《集合论与图论》第25讲

《集合论与图论》第25讲 6 定理12.7 定理12.7: 对图G进行χ(G)-着色,设 Vi={v|v∈V(G)∧v着颜色i}, i=1,2,…, χ(G), 则Π={V1,V2,…,Vχ(G)}是V(G)的划分. # 定理12.7’:对图G进行χ(G)-着色,设 R={| u,v∈V(G)∧u,v着同样颜色}, 则 R是V(G)上等价关系. # 说明: Vi中的点构成“独立集”

x(G)上界 定理125:X(G)≤△(G)+1 证明:WVeV(G,Te(v)={u|(u)EE(G) c)△(G),给I)中顶点着色至多需 要A(G种颜色,所以至少还剩一种颜色可 用来给v着色.# 定理126(Boks:若G连通非完全图Kn (≥3)非奇圈,则(G)≤△(G).# 说明:n=1G=K1n=2:连通→G=K 《集合论与图论》第25讲

《集合论与图论》第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连通非完全图Kn (n≥3)非奇圈, 则χ(G) ≤ Δ(G). # 说明: n=1⇒G=K1, n=2: 连通⇒G=K2

例121( Petersen图) 例121: Petersen图x=3 解1:由 Brooks定理,x≤A=3.又图中有奇 圈,x23.所以x=3.# 解2:存在如下3-着色,xA=3又图中有 奇圈,X≥3.所以x=3.# 思考题:至少有3点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的) 《集合论与图论》第25讲

《集合论与图论》第25讲 8 例12.1(Petersen图) 例12.1: Petersen图χ=3. 解1: 由Brooks定理, χ≤Δ=3. 又图中有奇 圈, χ≥3. 所以χ=3. # 解2: 存在如下3-着色, χ≤Δ=3. 又图中有 奇圈, χ≥3. 所以χ=3. # 思考题: 至少有3点同色? 在同构意义下着色是唯一的? (着色导出的划分是同构的)

地图 地图:连通无桥平面图的平面嵌入及其所 有的面称为(平面)地图 国家:平面地图的面 秦相邻:两个国家的公共边界至少有一条公 共边 k-面着色,k色地图,面色数x(G) 《集合论与图论》第25讲

《集合论与图论》第25讲 9 地图 地图: 连通无桥平面图的平面嵌入及其所 有的面称为(平面)地图 国家: 平面地图的面 相邻: 两个国家的公共边界至少有一条公 共边 k-面着色, k-色地图, 面色数χ*(G)

面着色与对偶图点着色 婚定理1213:地图G可k-面着色⊙对偶图 G*可k-着色.# 婚定理1214连通无环平面图G可K面着色 台对偶图G*可K着色.# 研究平面图面着色◇→研究平面图点着色 《集合论与图论》第25讲

《集合论与图论》第25讲 10 面着色与对偶图点着色 定理12.13: 地图G可k-面着色 ⇔ 对偶图 G*可k-着色. # 定理12.14: 连通无环平面图G可k-面着色 ⇔ 对偶图G*可k-着色. # 研究平面图面着色⇔研究平面图点着色