第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偶数