图的着色
文章目录
着色
着色：给图的某类元素(点,边,面)中的每个指定1种颜色,使得相邻元素有不同颜色
点着色
k-可着色的：能用k种颜色着色
k-色图：是k-可着色的，不是(k-1)可着色的
点色数：着色所需的最少颜色数，记作 χ ( G ) \chi(G) χ(G)
常见图的点色数
-
χ ( G ) = 1 ⇔ G 是 零 图 \chi(G)=1\Harr G是零图 χ(G)=1⇔G是零图
-
χ ( K n ) = N \chi(K_n)=N χ(Kn)=N
-
χ ( G ) = 2 ⇔ G 是 非 零 图 二 部 图 \chi(G)=2 \Harr G是非零图二部图 χ(G)=2⇔G是非零图二部图
-
G 是 2 − 可 着 色 的 ⇔ G 是 二 部 图 ⇔ G 无 奇 圈 G是2-可着色的\Harr G是二部图 \Harr G无奇圈 G是2−可着色的⇔G是二部图⇔G无奇圈
-
χ ( C n ) = { 2 n 偶 数 3 n 奇 数 \chi(C_n)= \begin {cases} 2 & n偶数\\ 3 & n奇数 \end {cases} χ(Cn)={23n偶数n奇数
-
χ ( W n ) = { 3 n 奇 数 4 n 偶 数 \chi(W_n)= \begin {cases} 3 & n奇数\\ 4 & n偶数 \end {cases} χ(Wn)={34n奇数n偶数
定理12.7：对图G进行 χ ( G ) − 着 色 \chi(G)-着色 χ(G)−着色，得到不同着色的点集为划分
定理12.5：$\chi(G)\le \varDelta(G)+1 $
定理12.6：若连通图G不是完全图 K 3 ( n ≥ 3 ) K_3(n\ge3) K3(n≥3)也不是奇圈，则 χ ( G ) ≤ Δ ( G ) \chi(G)\le\varDelta(G) χ(G)≤Δ(G)
Peterson图
由定理12.6 小于等于3
由奇圈，则大于等于3
综上，点色数为3
安排期末考试问题
顶点代表课，边代表这些课有公共学生，染色数代表排课时间段
地图的着色与平面图的点着色
地图：连通无桥平面图的平面嵌入及其所有的面称为(平面)地图
k-面可着色：可用k种颜色对平面地图着色
k-色地图：n是k-面可着色的,但不是(k-1)-面可着色的
面色数： χ ∗ ( G ) \chi^*(G) χ∗(G)
定理12.13
定理12.13：地图G是k-面可着色的⇔ 对偶图G*是k-可着色的.
四色定理
定理12.17：任何平面图都是4-可着色的
边着色
边色数： χ ′ ( G ) \chi'(G) χ′(G)
定理12.17：G是简单图，则 Δ ( G ) ≤ χ ′ ( G ) ≤ Δ ( G ) + 1 \varDelta(G)\le\chi'(G)\le\varDelta(G)+1 Δ(G)≤χ′(G)≤Δ(G)+1
G = < V 1 , V 2 , E > 是 二 部 图 ， 则 χ ′ ( G ) = Δ ( G ) G=<V_1,V_2,E>是二部图，则\chi'(G)=\varDelta(G) G=<V1,V2,E>是二部图，则χ′(G)=Δ(G)
n>1时，
χ
′
(
K
n
)
=
{
Δ
(
G
)
+
1
=
n
n
为
奇
数
Δ
(
G
)
=
n
−
1
n
为
偶
数
\chi'(K_n)= \begin{cases} \varDelta(G)+1=n &n为奇数\\ \varDelta(G)=n-1 &n为偶数 \end{cases}
χ′(Kn)={Δ(G)+1=nΔ(G)=n−1n为奇数n为偶数
排课问题
n个教师排m个班的课 ，每个老师每次只能给1个班上课，每个班每次只能听1个老师上课，则利用
二部图，至少排多少课为边色数，同色边代表上课可以同时进行
当节数不增加时，需要教室数最少，不同染色方案时同色边数量最大的值最小
n结论：有l门课程，被安排在p节课中，则每节课时平均有l/p门课同时上课，可以证明如下结论成立：
总存在一个排课方案，使得任意一节课时最多使用{l/p}间教室。
色多项式
f ( G , k ) = G 的 不 同 k − 着 色 方 案 的 总 数 f(G,k)=G的不同k-着色方案的总数 f(G,k)=G的不同k−着色方案的总数
求色数多项式
零图： f ( N n , k ) = k n f(N_n,k)=k^n f(Nn,k)=kn
完全图： f ( K n , k ) = k ( k − 1 ) . . . ( k − n 1 ) = n ! C k n f(K_n,k)=k(k-1)...(k-n_1)=n!C^n_k f(Kn,k)=k(k−1)...(k−n1)=n!Ckn
推论: f ( K n , k ) = f ( K n − 1 , k ) ( k − n + 1 ) ) , n ≥ 2 f(K_n,k)=f(K_{n-1,k})(k-n+1)),n\ge2 f(Kn,k)=f(Kn−1,k)(k−n+1)),n≥2
色多项式递推公式
定理12.9：KaTeX parse error: Undefined control sequence: \e at position 24: …(G\ U\ e,k)+f(G\̲e̲,k),e\notin E(G…
KaTeX parse error: Undefined control sequence: \e at position 20: …k)=f(G-e,k)-f(G\̲e̲,k),e\in E(G)
色多项式的性质
- 各项系数的符号是正负交替的
- k n k^n kn项的系数是
- k n − 1 k^{n-1} kn−1项系数是-m，m是G中的边数
- k 0 k^0 k0项的系数是0
- 系数非0项的最低次幂是 k p k^p kp,p是连通分支数
定理12.11
T是n阶树 ⇔ f ( T , k ) = k ( k − 1 ) n − 1 \Harr f(T,k)=k(k-1)^{n-1} ⇔f(T,k)=k(k−1)n−1
定理12.12
f ( C n , k ) = ( k − 1 ) + ( − 1 ) n ( k − 1 ) f(C_n,k)=(k-1)+(-1)^n(k-1) f(Cn,k)=(k−1)+(−1)n(k−1)