§6.5染色应用举例一求图的边色数及色数的算法 一、排课表问题一求二部图的正常z(G)边染色 1.问题:有m位教师x1,x2,…,xm,n个班级y,y2,…,yn。教师x每周需要给班级巧上 P次(节)课。要求制订一张周课时尽可能少的课程表 2.图论模型:构造二部图G=(X,F),其中X={x1,x2,…,xm},Y={y,y2,…,yn} 顶点x与y之间连pn条边。 一个课时的安排方案对应于二部图G的一个匹配。排课表问题等价于:将E(G)划分成 些匹配,使得匹配的数目尽可能地少 按x'(G)的定义,这个最小的数目便是x(G)。由定理621,x'(G)=△(G)。因此, 排课表问题等价于:求二部图G的边正常△(G)染色 如§6.1中所述,虽然求简单图的正常(Δ+1)边染色存在多项式时间算法,但求简 单图G的边色数z'(G)及其相应的正常边染色是一个NPC问题28。尽管如此,求二部图的 边正常Δ染色却有多项式时间算法。求图的边色数的近似算法可参考文献[29}51] 28]1. Holyer, The NP-completeness of edge-coloring, SIAMJ. Computing, 10: 4(1981),718-72 29E. Petrank, The hardness of approximation: gap location, Computational Complexity, 4 (1994),133-157 30]D. Leven and Z. Galil, NP completeness of finding the chromatic index of regular graphs, J Algorithms, 4(1983)35-44 31]P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan, Structure in approximation classes, SIAM J.Comp.,28(1999),1759-1782 32J. Misra and D. Gries, A constructive proof of Vizing s theorem. Inform. Process. Lett. 41 (1992),131-13 33]0. Terada, and T. Nishizeki, Approximate algorithms for the edge-coloring of graphs, Trans Inst. Eletron. Commun. Engr: Japan J65-D, 11(1982), 1382-1389 34M. Chrobak, and T. Nishizeki, Improved edge-coloring algorithms for planar graphs, J Algorithms, 11(1990), 102-116 35]I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Perennes, P. Persiano and H. Rivano Approximate constrained bipartite edge coloring, Discrete Applied Mathematics, 143(2004), 54-61 36] M.R. Salavatipour, A polynomial time algorithm for strong edge coloring of partial k-trees, Discrete Applied Mathematics, 143(2004), 285-291 37D.. Grable, A Panconesi, Nearly optimal distributed edge coloring inO(log log n)rounds Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January (1997),278-285 38] Yijie Han, Weifa Liang and Xiaojun Shen, Very fast parallel algorithms for approximate edge coloring, Discrete Applied Mathematics, 108(2001), 227-238 39]M. Furer and B. Raghavachari, Parallel edge coloring approximation, Parallel Process. Lett 6(1996),321-329
1 §6.5 染色应用举例—求图的边色数及色数的算法 一、排课表问题—求二部图的正常 χ′(G)边染色 1. 问题： 有 m 位教师 m x , x , , x 1 2 " ，n 个班级 n y , y , , y 1 2 " 。教师 xi 每周需要给班级 yj上 pij 次（节）课。要求制订一张周课时尽可能少的课程表。 2. 图论模型：构造二部图G = (X ,Y ) ，其中 X＝{ m x , x , , x 1 2 " }，Y＝{ n y , y , , y 1 2 " }， 顶点 i x 与 j y 之间连 pij 条边。 一个课时的安排方案对应于二部图 G 的一个匹配。排课表问题等价于：将 E(G)划分成 一些匹配，使得匹配的数目尽可能地少。 按 χ′(G)的定义，这个最小的数目便是 χ′(G)。由定理 6.2.1， χ′() () G G = Δ 。因此， 排课表问题等价于：求二部图 G 的边正常 Δ(G) 染色。 如§6.1 中所述，虽然求简单图的正常（ Δ +1）边染色存在多项式时间算法，但求简 单图 G 的边色数 χ′(G)及其相应的正常边染色是一个 NPC 问题[28]。尽管如此，求二部图的 边正常 Δ 染色却有多项式时间算法。求图的边色数的近似算法可参考文献[29]~[51]。 [28] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Computing, 10: 4(1981), 718-720. [29] E. Petrank, The hardness of approximation: gap location, Computational Complexity, 4 (1994), 133-157. [30] D. Leven and Z. Galil, NP completeness of finding the chromatic index of regular graphs, J. Algorithms, 4(1983) 35-44. [31] P. Crescenzi, V. Kann, R. Silvestri, and L. Trevisan, Structure in approximation classes, SIAM J. Comp., 28 (1999), 1759-1782. [32] J. Misra and D. Gries, A constructive proof of Vizing's theorem. Inform. Process. Lett. 41 (1992), 131-133. [33] O. Terada, and T. Nishizeki, Approximate algorithms for the edge-coloring of graphs, Trans. Inst. Eletron. Commun. Engr. Japan J65-D, 11(1982), 1382-1389. [34] M. Chrobak, and T. Nishizeki, Improved edge-coloring algorithms for planar graphs, J. Algorithms, 11(1990), 102-116. [35] I. Caragiannis, A. Ferreira, C. Kaklamanis, S. Perennes, P. Persiano and H. Rivano, Approximate constrained bipartite edge coloring, Discrete Applied Mathematics, 143(2004), 54-61 [36] M. R. Salavatipour, A polynomial time algorithm for strong edge coloring of partial k-trees, Discrete Applied Mathematics, 143(2004), 285-291. [37] D.A. Grable, A. Panconesi, Nearly optimal distributed edge coloring in O (log log n) rounds, Proceedings of the Eighth Annual ACM-SIAM Symposium on Discrete Algorithms, January, (1997), 278–285. [38] Yijie Han, Weifa Liang and Xiaojun Shen, Very fast parallel algorithms for approximate edge coloring, Discrete Applied Mathematics, 108(2001), 227-238. [39] M. Fürer and B. Raghavachari, Parallel edge coloring approximation, Parallel Process. Lett. , 6 (1996), 321–329
[40] H.J. Karloff and D B. Shmoys, Efficient parallel algorithms for edge coloring problems. J Algorithms 8(1987), 39-52 41 W. Liang, Fast parallel algorithms for the approximate edge-coloring problem. Inform Process.len:.56(1995),333-338 42]W. Liang, X. Shen and Q. Hu, Parallel algorithms for the edge-coloring and edge-coloring update problems. J. Parallel Distrib. Comput. 32(1996), 66-73 43]R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci. 49(1994), 478-516 [ 44]D. Bertsimas, C-P. Teo, andR. Vohra, On dependent randomized rounding algorithms, Proc 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci 084, Springer-Verlag, (1996), 330-344 45 M K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Theory 8(1984),123-127 [46]DS. Hochbaum, T. Nishizeki and D B. Shmoys, Better than"Best Possible"algorithm to edge color multi graphs, Journal of AlgorithmS, 7(1986), 79-104 [47 T. Nishizeki and K. Kashiwagi, On the 1. I edge-coloring of multigraphs, SIAMJ. Disc Mamh,3(1990),391-410 [48]J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory(SerB),68(1996),233-254 [49]x. Zhou H. Susuki, and T. Nishizeki, A linear algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 20(1996), 174-201 50]X. Zhou H. Susuki, and T. Nishizeki, An NC parallel algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 23(1997), 359-374 51]B Berger and J Rompel, Simulating(log n-wise independence in NC. J. ACM 38(1991), 026-1046 3.求二部图G=(X,Y)的边正常△(G)染色的算法 ●算法思想:给G添加必要的顶点使得|XHY,再添加必要的边使得G成为△(G)正 则二部图,所得图记为G,然后反复运用匈牙利算法求G的完美匹配。由第3章Knig 定理,G存在完美匹配。每求出G的一个完美匹配,便可用一种颜色给这个完美匹 配的边染色。因为共可求得G的△(G)个边不重的完美匹配,故可得G(从而G)的 边正常△(G)染色 二部图边染色算法:求二部图的边正常△(G)染色(求二部图的△(G)个边不交的匹配)。 输入:二部图G=(X,Y) 输出:G的边正常△G)染色(△(G)个边不交的匹配) 第0步:添加顶点使得X=Y1,所得图记为G 第1步:若Δ(G)=δ(G),令k=1,转第3步;否则,转第2步
2 [40] H.J. Karloff and D.B. Shmoys, Efficient parallel algorithms for edge coloring problems. J. Algorithms 8 (1987), 39–52. [41] W. Liang, Fast parallel algorithms for the approximate edge-coloring problem. Inform. Process. Lett. 56 (1995), 333–338. [42] W. Liang, X. Shen and Q. Hu, Parallel algorithms for the edge-coloring and edge-coloring update problems. J. Parallel Distrib. Comput. 32 (1996), 66-73. [43] R. Motwani, J. Naor and M. Naor, The probabilistic method yields deterministic parallel algorithms. J. Comput. System Sci. 49 (1994), 478-516. [44] D. Bertsimas, C-P. Teo, and R. Vohra, On dependent randomized rounding algorithms, Proc. 5th Int. Conf. on Integer Prog. and Combinatorial Optimization, Lecture Notes in Comput. Sci. 1084, Springer-Verlag, (1996), 330-344. [45] M.K. Goldberg, Edge-colorings of multigraphs: recoloring technique, J. Graph Theory, 8(1984), 123-127. [46] D.S. Hochbaum, T. Nishizeki and D.B. Shmoys, Better than “Best Possible” algorithm to edge color multi graphs, Journal of Algorithms, 7(1986), 79-104 [47] T. Nishizeki and K. Kashiwagi, On the 1.1 edge-coloring of multigraphs, SIAM J. Disc. Math. , 3(1990), 391-410. [48] J. Kahn, Asymptotics of the chromatic index for multigraphs, Journal of Combinatorial Theory (Ser. B), 68(1996), 233-254. [49] X. Zhou H. Susuki, and T. Nishizeki, A linear algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 20(1996), 174-201. [50] X. Zhou H. Susuki, and T. Nishizeki, An NC parallel algorithm for edge-coloring series-parallel multigraphs, J. Algorithms, 23(1997), 359-374. [51] B. Berger and J. Rompel, Simulating (logc n)-wise independence in NC. J. ACM 38 (1991), 1026–1046. 3. 求二部图G = (X ,Y ) 的边正常 Δ(G) 染色的算法 z 算法思想：给 G 添加必要的顶点使得| X |=|Y |，再添加必要的边使得 G 成为 Δ(G) 正 则二部图，所得图记为 * G ，然后反复运用匈牙利算法求 * G 的完美匹配。由第 3 章 König 定理， * G 存在完美匹配。每求出 * G 的一个完美匹配，便可用一种颜色给这个完美匹 配的边染色。因为共可求得 * G 的 Δ(G) 个边不重的完美匹配，故可得 * G （从而 G）的 边正常 Δ(G) 染色。 z 二部图边染色算法：求二部图的边正常 Δ(G) 染色(求二部图的 Δ(G) 个边不交的匹配)。 输入：二部图 G=(X,Y) 输出：G 的边正常 Δ(G) 染色（ Δ(G) 个边不交的匹配） 第 0 步：添加顶点使得|X|=|Y|，所得图记为 * G 。 第 1 步：若 ( ) ( ) * * Δ G = δ G ，令k = 1，转第 3 步；否则，转第 2 步
第2步:取x∈X,y∈Y,使得d(x)=mind.(x,),d(y0)= mind(y),令 G:=G+x0y,转第1步。 第3步:任取G的一个匹配M。 第4步:若X已M饱和,则输出当前的完美匹配,转第7步;否则取X中一个M不饱和 点u,置S:={m},T=φ。 第5步:在N(S)T中取一点y 第6步:若y是M饱和的,则存在y∈M,置S:=SU{},T=TU{y},转第5步; 否则,存在一条M可扩路P(u,y),置M:=M⊕E(P),转第4步。 第7步:若k=Δ,则停止;否则,令k:=k+1,G:=G"\M,转第3步 设|XPY|。因匈牙利算法的时间复杂性为O(XP),而第1步和第2步的加边循环 不超过|X|·△次,故该算法是多项式时间算法。 4.带有约束的排课表问题 设学校每周有l节课,安排在一张有p节课时的课表中(前面的方法求得一个Δ节课时 的课表)。这样,平均每一课时要上-节课,因此需要-间教室。比如,l=510, P P 510 p=20,则需要 P20|=26间教室。 问题:可否在一张有P节课时的课表里安排l节课,使得在一节课时内至多用-间教室? 下面的引理见第3章习题。 引理651设M和N是图G的两个无公共边的匹配,并且M卜|N|,则存在G的无公共 边的匹配M和N,使得|M'HM|-1,|NHN|+1,且M"UN′=MUN。 定理65.1若图G是一个二部图,且p≥△(G),则G中存在p个无公共边的匹配 M1M2,…Mn,使得E=M1∪M2U…∪Mn,且对每个i(=1,2,…P)均有 ≤M1 P 证明:因图G是二部图,故由本章定理61.1,边集E(G)可划分为△个匹配M1,M2…,M 因而对任何p≥M(G),G中存在P个无公共边的匹配M,M2,…,MA,MA1…,MD(其 中MA=…=Mn=),使得E(G)=∪M。对这些匹配反复运用引理651,便可得 到满足定理要求的匹配。证毕。 这个定理对前述带约東排课表问题给出了肯定回答。同时也给出了求所需教室数最少的 P课时课表的方法:先按二部图边染色算法求出相应二部图的一个正常△(G)边染色,然后
3 第 2 步：取 x0 ∈ X ， y0 ∈Y ，使得 * ( ) min * ( ) 0 G i G x X d x d x i ∈ = ， * ( ) min * ( ) 0 G i G y Y d y d y i ∈ = ，令 0 0 * * G := G + x y ，转第 1 步。 第 3 步：任取 * G 的一个匹配 M。 第 4 步：若 X 已 M 饱和，则输出当前的完美匹配，转第 7 步；否则取 X 中一个 M 不饱和 点 u，置 S := {u}，T := φ 。 第 5 步：在 N(S) \ T 中取一点 y. 第 6 步：若 y 是 M 饱和的，则存在 yz ∈ M ，置 S := S ∪{z}，T := T ∪{y}，转第 5 步； 否则，存在一条 M 可扩路 P(u, y) ，置 M := M ⊕ E(P) ，转第 4 步。 第 7 步：若k = Δ ，则停止；否则，令k := k + 1，G : G \ M * * = ，转第 3 步。 设| || | X ≥ Y 。因匈牙利算法的时间复杂性为 3 O X (| | ) ，而第 1 步和第 2 步的加边循环 不超过| X | ⋅Δ 次，故该算法是多项式时间算法。 4. 带有约束的排课表问题 设学校每周有 l 节课，安排在一张有 p 节课时的课表中（前面的方法求得一个 Δ 节课时 的课表）。这样，平均每一课时要上 ⎥ ⎥ ⎤ ⎢ ⎢ ⎡ p l 节课，因此需要 ⎥ ⎥ ⎤ ⎢ ⎢ ⎡ p l 间教室。比如， l = 510 ， p = 20，则需要 26 20 510 =⎥ ⎥ ⎤ ⎢ ⎢ ⎡ =⎥ ⎥ ⎤ ⎢ ⎢ ⎡ p l 间教室。 问题：可否在一张有 p 节课时的课表里安排 l 节课，使得在一节课时内至多用 ⎥ ⎥ ⎤ ⎢ ⎢ ⎡ p l 间教室？ 下面的引理见第 3 章习题。 引理 6.5.1 设 M 和 N 是图 G 的两个无公共边的匹配，并且| M |>| N |，则存在 G 的无公共 边的匹配 M ′ 和 N′ ，使得| M ′ |=| M | −1，| N′ |=| N | +1，且 M ′∪ N′ = M ∪ N 。 定理 6.5.1 若图 G 是一个二部图，且 p ≥ Δ( ) G ，则 G 中存在 p 个无公共边的匹配 M M "M p , , 1 2 ，使得 E = M1 ∪ M2 ∪"∪ M p ，且对每个i (i = 1,2,", p)均有 ⎥ ⎥ ⎤ ⎢ ⎢ ⎡ ≤ ≤ ⎥ ⎦ ⎥ ⎢ ⎣ ⎢ p G M p G i ( ) | | ε ( ) ε 。 证明：因图G是二部图，故由本章定理6.1.1，边集 E(G) 可划分为 Δ 个匹配 Δ M ′, M ′, , M ′ 1 2 " ， 因而对任何 p ≥ Δ(G) ，G 中存在 p 个无公共边的匹配 , , , , 1 2 Δ M ′ M ′ " M ′ M M p ′ ′ Δ+ , , 1 " （其 中 MΔ ′ +1 = " = M ′ p = φ ），使得 ∪ p i E G Mi 1 ( ) = = ′。对这些匹配反复运用引理 6.5.1，便可得 到满足定理要求的匹配。证毕。 这个定理对前述带约束排课表问题给出了肯定回答。同时也给出了求所需教室数最少的 p 课时课表的方法：先按二部图边染色算法求出相应二部图的一个正常 Δ(G) 边染色，然后
反复运用引理6.5.1对其进行调整,最终使得染不同颜色的两个边集所含边数至多相差1。 例651设有4个教师x,x2,x,x和5个班级y,2y3,y4,y,教学矩阵T=(2)表示如下 x1(20110 010 01110 问:(1)课表至少需要几课时? (2)按二部图边染色算法给出一个课时数最少的课表。 (3)在课时数最少的前提下,给出需教室数最少的课表方案。 解:构造二部图如下图1: x 图1 由于Δ(G)=4,故课表至少需4课时 执行二部图边染色算法得G的4个边不交的匹配(如图2)。相应的一个4课时课表如下 y V4 x4 y4 ys 按这张课表安排,需4个教室,但因a(G)=1.1|=11=3,由定理641,可 排出一张只需3个教室的4课时课表。事实上,将教师x4在第1课时的课调到第3课时而 将教师x2在第3课时的课与第1课时对调即可。从二部图的匹配上来看,是将第1课时和 第3课时对应的匹配施行了一次引理641的操作。一张只需3个教室的4课时课表如下: 2 4 y y y x3 y y y
4 反复运用引理 6.5.1 对其进行调整，最终使得染不同颜色的两个边集所含边数至多相差 1。 例 6.5.1 设有 4 个教师 x1, x2, x3, x4 和 5 个班级 y1, y2, y3, y4, y5，教学矩阵 ( )ij T = t 表示如下： ⎟ ⎟ ⎟ ⎟ ⎟ ⎠ ⎞ ⎜ ⎜ ⎜ ⎜ ⎜ ⎝ ⎛ = 0 0 0 1 1 0 1 1 1 0 0 1 0 1 0 2 0 1 1 0 4 3 2 1 1 2 3 4 5 x x x x y y y y y T 问：（1）课表至少需要几课时？ （2）按二部图边染色算法给出一个课时数最少的课表。 （3）在课时数最少的前提下，给出需教室数最少的课表方案。 解：构造二部图如下图 1： 图 1 图 2 由于 Δ(G) = 4 ，故课表至少需 4 课时。 执行二部图边染色算法得 G 的 4 个边不交的匹配(如图 2)。相应的一个 4 课时课表如下： 教师 课时 1 2 3 4 x1 y1 y1 y3 y4 x2 y2 y4 x3 y3 y4 y2 x4 y4 y5 按这张课表安排，需 4 个教室。但因ε (G) = 11， 3 4 11 =⎥ ⎥ ⎤ ⎢ ⎢ ⎡ =⎥ ⎥ ⎤ ⎢ ⎢ ⎡ p ε ，由定理 6.4.1，可 排出一张只需 3 个教室的 4 课时课表。事实上，将教师 4 x 在第 1 课时的课调到第 3 课时而 将教师 2 x 在第 3 课时的课与第 1 课时对调即可。从二部图的匹配上来看，是将第 1 课时和 第 3 课时对应的匹配施行了一次引理 6.4.1 的操作。一张只需 3 个教室的 4 课时课表如下： 教师 课时 1 2 3 4 x1 y1 y1 y3 y4 x2 y4 y2 x3 y3 y4 y2 x4 y5 y4 x4 x3 x2 x1 y1 y2 y3 y4 y5 x4 x3 x2 x1 y1 y2 y3 y4 y5
二、点染色的应用及正常z(G)点染色的求法 应用背景举例 (1)考试安排问题 某校有n门选修课L1,L2,…,L需进行期末考试,同一个学生不能在同一天里参加两门 或两门以上课程的考试。试问:该校的期末考试至少需要几天?如何安排? 图论模型:构造图G=(,E如下:(G)={L1,L2,…,Ln},LL,∈E(G)当且仅当课 程L和L被同一学生选修 将同一天的考试课程在G中对应的顶点染同一种色,则考试安排相当于对G进行顶点 正常染色。所求最少天数即为G的点色数x(G)。问题化为:求图G的正常x(G)点染色 (2)电视频道分配问题 某地区有n家电视发射台T1,T2,…,T,主管部门给每家电视台分配一个发射频道。为 排除同频干扰,使用相同频道的发射台之间相距必须大于一定的距离d。试问:该地区至少 需要多少个频道?如何分配? 图论模型:构造图G=(,E如下:(G)={7,T2,…,T},TT∈E(G)当且仅当 射台T和T的距离不超过d 考虑G图的正常点染色。易见染同一种色的顶点可分配给同一频道。反之,按要求分 配一个频道,相当于给G中相应的顶点染同一种色。因此,频道分配相当于对G进行顶点 正常染色。所求最少频道数即为点色数x(G)。问题化为:求图G的正常z(G)点染色。 (3)储藏问题 某公司生产n种化学品C1C2,…,Cn,其中某些制品不能存放在同一个仓库中。问至 少需要多少个仓库?如何分配存放? 图论模型:构造图G=(,E)如下:H(G)={C1,C2,…,Cn},CC,∈E(G)当且仅当 制品C,和C,不能放在同一仓库中。 若干制品可放在同一仓库当且仅当它们在G中对应的顶点可染同一种色。可见给这些 产品分配仓库相当于对G进行正常点染色。所需的最少仓库数即为G的点色数(G)。问 题化为:求图G的正常z(G)点染色 对既不是完全图又不是奇圈的图G,利用 Brooks定理的证明可以得到求G的顶点△(G) 正常染色的一个有效算法。但是,在一般情况下,△(G)与z(G)并不相等。求任意图的 正常z(G)点染色是一个NPC问题1,目前没有多项式时间精确算法,仅有一些适用于小 规模问题的非多项式时间算法和一些多项式时间近似算法。遗憾的是,迄今为止找到的多项 式时间近似算法其近似比都不等于常数。可见,从计算复杂性的角度来看,图的点染色问题 是如此困难,以至于连近似比等于常数的多项式时间近似算法都难以找到。实际上,已经证
5 二、点染色的应用及正常 χ(G) 点染色的求法 1．应用背景举例 （1）考试安排问题 某校有 n 门选修课 L L Ln , , , 1 2 " 需进行期末考试，同一个学生不能在同一天里参加两门 或两门以上课程的考试。试问：该校的期末考试至少需要几天？如何安排？ 图论模型：构造图 G＝(V, E)如下：V (G) = { L L Ln , , , 1 2 " }，L L E(G) i j ∈ 当且仅当课 程 Li 和 Lj 被同一学生选修。 将同一天的考试课程在 G 中对应的顶点染同一种色，则考试安排相当于对 G 进行顶点 正常染色。所求最少天数即为 G 的点色数 χ(G) 。问题化为：求图 G 的正常 χ(G) 点染色。 （2）电视频道分配问题 某地区有 n 家电视发射台T T Tn , , , 1 2 " ，主管部门给每家电视台分配一个发射频道。为 排除同频干扰，使用相同频道的发射台之间相距必须大于一定的距离 d。试问：该地区至少 需要多少个频道？如何分配？ 图论模型：构造图 G＝(V, E)如下：V (G) = {T T Tn , , , 1 2 " }，T T E(G) i j ∈ 当且仅当发 射台Ti 和Tj 的距离不超过 d。 考虑 G 图的正常点染色。易见染同一种色的顶点可分配给同一频道。反之，按要求分 配一个频道，相当于给 G 中相应的顶点染同一种色。因此，频道分配相当于对 G 进行顶点 正常染色。所求最少频道数即为点色数 χ(G) 。问题化为：求图 G 的正常 χ(G) 点染色。 （3）储藏问题 某公司生产 n 种化学品C C Cn , , , 1 2 " ，其中某些制品不能存放在同一个仓库中。问至 少需要多少个仓库？如何分配存放？ 图论模型：构造图 G＝(V, E)如下：V(G) = {C C Cn , , , 1 2 " }，C C E(G) i j ∈ 当且仅当 制品Ci 和Cj 不能放在同一仓库中。 若干制品可放在同一仓库当且仅当它们在 G 中对应的顶点可染同一种色。可见给这些 产品分配仓库相当于对 G 进行正常点染色。所需的最少仓库数即为 G 的点色数 χ(G) 。问 题化为：求图 G 的正常 χ(G) 点染色。 对既不是完全图又不是奇圈的图G，利用Brooks定理的证明可以得到求G的顶点 Δ(G)- 正常染色的一个有效算法[116]。但是，在一般情况下，Δ(G)与 χ(G) 并不相等。求任意图的 正常 χ(G) 点染色是一个 NPC 问题[116]，目前没有多项式时间精确算法，仅有一些适用于小 规模问题的非多项式时间算法和一些多项式时间近似算法。遗憾的是，迄今为止找到的多项 式时间近似算法其近似比都不等于常数。可见，从计算复杂性的角度来看，图的点染色问题 是如此困难，以至于连近似比等于常数的多项式时间近似算法都难以找到。实际上，已经证