着色(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,有公共边界