§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]，目前没有多项式时间精确算法，仅有一些适用于小 规模问题的非多项式时间算法和一些多项式时间近似算法。遗憾的是，迄今为止找到的多项 式时间近似算法其近似比都不等于常数。可见，从计算复杂性的角度来看，图的点染色问题 是如此困难，以至于连近似比等于常数的多项式时间近似算法都难以找到。实际上，已经证
明,如果存在多项式时间染色算法使得对每个图G都可使用不多于2(G)种色进行正常顶 点染色,则必定存在G的z(G)顶点染色有效算法1m1。这表明,对图的点染色问题,找 近似比等于常数的多项式时间近似算法与找(G)顶点染色的(有效)精确算法一样困难。 下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。更多的算法可参见文 献[52}[115],其中[52}-{58]是与图的点染色算法有关的专著,[59}-[72]研究图的点染色问 题的各种精确算法,[73}-[89研究图的点染色问题的近似算法及其性能,在不同条件下给出 了较低近似比的染色算法,[9o-[1l将邻域方法、禁忌搜索和局部搜索方法、模拟退火法 人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。 [12[15讨论点染色的相关计算复杂性问题。 52 G Chartrand, O. R Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc New York,(1993),283-310 53 M.R. Garey and D.s. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979 54] D.S. Hochbaum, Approximation Algorithms for NP-hard ProblemS, International Thomson Publishing Inc,1997(影印本:NP难解问题的近似算法,世界图书出版公司) 55]N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, (1990),58-78 56]S Even, Algorithmic Combinatorics, Macmillan, New York, 1973 57]R. Gould, Graph Theory, Benjamin Cummings, Menlo, Park, CA(1988 58]D W. Matula, G. Marble, and J D. Isaacson, Graph colouring algorithms, in Graph Theory and Computing(Read Ed.), Academic Press, New York, (1972)109-122 59]D. Brelaz, New methods to color the vertices of a graph, Communications of the Association y,22(1979)251-256 [60 E.C.Sewell. An Improved algorithm for exact graph coloring, in"Cliques, Coloring and Satisfiability"(DIMACS Series in Discrete Mathematics and Theoretical Computer Science), 26(1996), 359-373. American Mathematical Society, Providence, RI, USA 161 D. Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and ApplicationS, 7(2)(2003), 131-140 [62]N. Christofides, An algorithm for the chromatic number of a graph, The Computer Journal, 4(1971),38-39 163 D G Corneil and B. Graham, An algorithm for determining the chromatic number of a graph, SIAM Journal on Computing, 2(1973), 211-218 64]D. Kirovski and M. Potkonjak, Efficient coloring of a large spectrum of graphs. In DAC 98 Proceedings of the 35th annual conference on Design automation, (1998), 427-432, ACM Press, New York. NY USA [65] Ojvind Johansson, Simple distributed A+l-coloring of graphs, Information Processing Letters,70(1999),229-232 [66]I M. Diaz and P. Zabala, A branch-and-cut algorithm for graph coloring, (2002), 55-62, Ithaca, New York. USA
6 明，如果存在多项式时间染色算法使得对每个图 G 都可使用不多于 2 (G) χ 种色进行正常顶 点染色，则必定存在 G 的 χ(G) 顶点染色有效算法[117][118]。这表明，对图的点染色问题，找 近似比等于常数的多项式时间近似算法与找 χ(G) 顶点染色的（有效）精确算法一样困难。 下面介绍点染色问题的几种非多项式时间算法和简单的近似算法。更多的算法可参见文 献[52]~[115]，其中[52]~[58]是与图的点染色算法有关的专著，[59]~[72]研究图的点染色问 题的各种精确算法，[73]~[89]研究图的点染色问题的近似算法及其性能，在不同条件下给出 了较低近似比的染色算法，[90]~[111]将邻域方法、禁忌搜索和局部搜索方法、模拟退火法、 人工神经网络、遗传算法、蚁群算法等方法以及其它一些启发式方法用于图的点染色问题。 [112]-[115]讨论点染色的相关计算复杂性问题。 [52] G. Chartrand, O. R. Oellermann, Applied and Algorithmic Graph Theory, McGraw-Hill, Inc., New York, (1993), 283-310. [53] M.R. Garey and D.S. Johnson, Computers and Intractibility: A Guide to the Theory of NP-Completeness, Freeman, New York, 1979. [54] D.S. Hochbaum, Approximation Algorithms for NP-hard Problems, International Thomson Publishing Inc., 1997 (影印本：NP 难解问题的近似算法，世界图书出版公司)。 [55] N. Christofides, Graph Theory: An Algorithmic Approach, Academic Press, New York, (1990), 58-78. [56] S. Even, Algorithmic Combinatorics, Macmillan, New York, 1973. [57] R. Gould, Graph Theory, Benjamin Cummings, Menlo, Park, CA(1988). [58] D.W. Matula, G. Marble, and J.D. Isaacson, Graph colouring algorithms, in Graph Theory and Computing (Read Ed.), Academic Press, New York, (1972) 109-122. [59] D. Brelaz, New methods to color the vertices of a graph, Communications of the Association for Computing Machinery, 22(1979), 251-256. [60] E.C.Sewell. An Improved algorithm for exact graph coloring, in “Cliques, Coloring and Satisfiability”. (DIMACS Series in Discrete Mathematics and Theoretical Computer Science), 26 (1996), 359-373. American Mathematical Society, Providence, RI, USA. [61] D. Eppstein, Small maximal independent sets and faster exact graph coloring, Journal of Graph Algorithms and Applications, 7(2) (2003), 131-140. [62] N. Christofides, An algorithm for the chromatic number of a graph, The Computer Journal, 14(1971), 38-39. [63] D. G. Corneil and B. Graham, An algorithm for determining the chromatic number of a graph, SIAM Journal on Computing, 2(1973), 211-218. [64] D. Kirovski and M. Potkonjak, Efficient coloring of a large spectrum of graphs. In DAC '98: Proceedings of the 35th annual conference on Design automation, (1998), 427-432, ACM Press, New York, NY, USA. [65] Ojvind Johansson, Simple distributed Δ +1-coloring of graphs, Information Processing Letters, 70(1999), 229-232. [66] I.M. Diaz and P. Zabala, A branch-and-cut algorithm for graph coloring, (2002), 55-62, Ithaca, New York, USA
[67] M. Caramia and P. Dell'Olmo. Bounding vertex coloring by truncated multistage branch and bound, Networks,44(4)(2004,231-242 168 M. Kubale and B. Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28(1985), 412-418 [ 69]A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS Journal On Computing, 8(4)(1996), 344-354 [70]SR. Vegdahl, Using node merging to enhance graph coloring In PLD/ 99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation (1999), 150-154, ACM Press, New York, NY, USA [71]F. Herrmann and A. Hertz, Finding the chromatic number by means of critical graphs Journal of Experimental Algorithmics, 7(2002), p10 [ G.A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, An unconstrained quadratic binary approach to the vertex coloring problem. Annals ofoperations Research, 139(1)(2005), 229-241 [73 A. Wigderaon, improving the performance guarantee for approximate graph coloring, Journal of the ACa,30(1983),729-735 174] B. Berger and J. Rompel. a better permance guarantee for approximate graph coloring Algorithmica, 5(1990), 459-466 75]M. M. Halldorsson, A still better performance guarantee for approximate graph coloring, Processing Letters, 45(1993),19-23 [76] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximabil ity -towards tight results, SIAMJ. Comp. 27(1998),804-915 [77]A Blum, and D Karger, An O(n)-coloring algorithm for 3-colorable graphs, Information Processing Letters, 61(1997), 49-53 78]L. J. Cowen, W. Goddard, and C. E. Jesurum, Coloring with defect, Proc. &th Ann ACM-SIAM Symp. on Discrete AlgorithmS, ACM-SIAM, (1997), 548-557 [79]R. Duh, and M. Furer, Approximation of k-set cover by semi-local optimization, Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, (1997), 256-265 80 D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, J. ACM, 45(1998), 246-265. E n Proceedings of the 35AnnuaI IEEE Symposium on Foundations of Computer Science, (1994), 2-13 81] Crivelevich, and B. Sudakov, Appr oximate coloring of uniform hypergraphs, Proc. 6th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 477-489 [82] T. Hofmeister, and H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci Lecture Notes in Comput. Sci. 1450, Springer-Verlag, (1998), 562-570 [83]U. Feige, and J. Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57(2)(1998),187-199 84]V. Kumar, Approximating circular arc colouring and bandwidth allocation in all-optical ring networks, Proc. Ist Int. Workshop on Approximation Algorithms for Combinatorial Problems ecture Notes in Comput. Sci., Springer-Verlag, (1998), 147-158
7 [67] M. Caramia and P. Dell'Olmo. Bounding vertex coloring by truncated multistage branch and bound, Networks, 44(4) (2004), 231-242. [68] M. Kubale and B. Jackowski. A generalized implicit enumeration algorithm for graph coloring. Communications of the ACM, 28 (1985), 412-418. [69] A. Mehrotra and M. Trick, A column generation approach for graph coloring. INFORMS Journal On Computing, 8(4) (1996), 344-354. [70] S.R. Vegdahl, Using node merging to enhance graph coloring. In PLDI '99: Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, (1999), 150-154, ACM Press, New York, NY, USA. [71] F. Herrmann and A. Hertz, Finding the chromatic number by means of critical graphs. Journal of Experimental Algorithmics, 7(2002), p10. [72] G.A. Kochenberger, F. Glover, B. Alidaee, and C. Rego, An unconstrained quadratic binary approach to the vertex coloring problem. Annals of Operations Research, 139(1) (2005), 229-241. [73] A. Wigderaon, improving the performance guarantee for approximate graph coloring, Journal of the ACM, 30(1983), 729-735. [74] B. Berger and J. Rompel. A better permance guarantee for approximate graph coloring. Algorithmica, 5(1990), 459-466. [75] M. M. Halldórsson, A still better performance guarantee for approximate graph coloring, Information Processing Letters，45(1993), 19-23. [76] M. Bellare, O. Goldreich, and M. Sudan, Free bits, PCPs and non-approximability - towards tight results, SIAM J. Comp. 27(1998), 804-915. [77] A. Blum, and D. Karger, An 3 14 O n( ) -coloring algorithm for 3-colorable graphs, Information Processing Letters，61(1997), 49-53. [78] L. J. Cowen, W. Goddard, and C. E. Jesurum, Coloring with defect, Proc. 8th Ann. ACM-SIAM Symp. on Discrete Algorithms, ACM-SIAM, (1997), 548-557. [79] R. Duh, and M. Fürer, Approximation of k-set cover by semi-local optimization, Proc. 29th Ann. ACM Symp. on Theory of Comp., ACM, (1997), 256-265. [80] D. Karger, R. Motwani, and M. Sudan, Approximate graph coloring by semidefinite programming, J. ACM，45(1998), 246-265. 或见 Proceedings of the 35th Annual IEEE Symposium on Foundations of Computer Science, (1994), 2-13. [81] M. Krivelevich, and B. Sudakov, Approximate coloring of uniform hypergraphs, Proc. 6th Ann. European Symp. on Algorithms, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 477-489. [82] T. Hofmeister, and H. Lefmann, Approximating maximum independent sets in uniform hypergraphs, Proc. 23rd International Symp. on Mathematical Foundations of Comput. Sci., Lecture Notes in Comput. Sci. 1450, Springer-Verlag, (1998), 562-570. [83] U. Feige, and J. Kilian, Zero knowledge and the chromatic number, Journal of Computer and System Sciences, 57(2)(1998), 187-199. [84] V. Kumar, Approximating circular arc colouring and bandwidth allocation in all-optical ring networks, Proc. 1st Int. Workshop on Approximation Algorithms for Combinatorial Problems, Lecture Notes in Comput. Sci., Springer-Verlag, (1998), 147-158
[85]S. Khanna, N Linial, and S Safra, On the hardness of approximating the chromatic number, Proc. 2nd Israel Symp. on Theory of Computing and Systems, IEEE Computer Society,(1993), 250-26C 86] C. Lund, and M. Yannakakis, On the hardness of approximating minimization problems, J ACM41(1994),960-981 [87]M. V. Marathe, H. Breu, H. B. Hunt Ill, S.S. Ravi, and D J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks, 25(1995), 59-68 [88]A. Blum, New Approximation algorithms for graph coloring, Journal of the ACM, 41(1994), 470-516 1891 A. Blum. Some tools for approximate 3-coloring. In Proceedings 3Ist IEEE Symposium on Foundations of Computer Science, pages 554-562, Los Angeles, CA, 1990. IEEE Computer 190] M. Laguna and R. Marti, A GRASP for coloring sparse graphs. Computational optimization and applications, 19(2)(2001), 165-178 91] Alon N, Krivelevich M, and Sudakov B, Coloring graphs with sparse neighborhoods Journal of Combinatorial Theory, Ser. B, 77(1999), 73-82 [92 Morgenstern C. and Shapiro H., Coloration neighborhood structures for general graph coloring. In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms (1990), 226-235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA 93] Avanthay C, Hertz A, and Zufferey N, a variable neighborhood search for graph coloring European journal of Operational Research, (2003) 94] Glass C.A. and Prugel-Bennett A, A polynomially searchable exponential neighbourhood for graph colouring. Journal ofthe Operational Research Society, 56(3)(2005), pp. 324-330 95] Hertz A and de Werra D, Using tabu search techniques for graph coloring. Computing, 39(4) (1987),345-351 96]Gonzalez-Velarde J and Laguna M, Tabu search with simple ejection chains for coloring graphs. Annals of Operations Research, 117(1-4)(2002), 165-174 [97] Chiarandini M. and Stutzle T, An application of iterated local search to graph coloring. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, edited by D.s. Johnson, A Mehrotra, and M. Trick, (2002), 112-125. Ithaca, New York, USA [98 Fleurent C and Ferland J, Object-oriented implementation of heuristics search methods for graph coloring, maximum clique, and satisfiability. vol 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996),619-652, American Mathematical Society, Providence, RI, USA 99]D de Werra, Lausanne, Heuristics for graph coloring. Computing Supplementum, 7(1990) 91-208 [100] Blas A D, Jagota A, and Hughey R, A range-compaction heuristic for graph coloring Journal of Heuristics, 9(3)(2003), 489-506 [101] Lewandowski G. and Condon A, Experiments with parallel graph coloring heuristics and applications of graph coloring. vol 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 309-334. American Mathematical Society, Providence, RI USA
8 [85] S. Khanna, N.Linial, and S. Safra, On the hardness of approximating the chromatic number, Proc. 2nd Israel Symp. on Theory of Computing and Systems, IEEE Computer Society, (1993), 250-260. [86] C. Lund, and M. Yannakakis, On the hardness of approximating minimization problems, J. ACM 41(1994), 960-981. [87] M. V. Marathe, H. Breu, H. B. Hunt III, S. S. Ravi, and D. J. Rosenkrantz, Simple heuristics for unit disk graphs, Networks，25(1995), 59-68. [88] A. Blum, New Appproximation algorithms for graph coloring, Journal of the ACM, 41(1994), 470-516. [89] A. Blum. Some tools for approximate 3-coloring. In Proceedings 31st IEEE Symposium on Foundations of Computer Science, pages 554-562, Los Angeles, CA, 1990. IEEE Computer Society. [90] M. Laguna and R. Martí, A GRASP for coloring sparse graphs. Computational optimization and applications, 19(2) (2001), 165-178. [91] Alon N., Krivelevich M., and Sudakov B. , Coloring graphs with sparse neighborhoods. Journal of Combinatorial Theory, Ser. B, 77(1999), 73-82. [92] Morgenstern C. and Shapiro H. , Coloration neighborhood structures for general graph coloring. In Proceedings of the first annual ACM-SIAM Symposium on Discrete algorithms, (1990), 226-235. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA. [93] Avanthay C., Hertz A., and Zufferey N. , A variable neighborhood search for graph coloring. European Journal of Operational Research, (2003). [94] Glass C.A. and Prügel-Bennett A. , A polynomially searchable exponential neighbourhood for graph colouring. Journal of the Operational Research Society, 56(3) (2005), pp. 324-330. [95] Hertz A. and de Werra D., Using tabu search techniques for graph coloring. Computing, 39(4) (1987), 345-351. [96] González-Velarde J. and Laguna M., Tabu search with simple ejection chains for coloring graphs. Annals of Operations Research, 117(1-4) (2002), 165-174. [97] Chiarandini M. and Stützle T. , An application of iterated local search to graph coloring. In Proceedings of the Computational Symposium on Graph Coloring and its Generalizations, edited by D.S. Johnson, A. Mehrotra, and M. Trick, (2002), 112-125. Ithaca, New York, USA. [98] Fleurent C. and Ferland J. , Object-oriented implementation of heuristics search methods for graph coloring, maximum clique, and satisfiability. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 619-652, American Mathematical Society, Providence, RI, USA. [99] D. de Werra, Lausanne, Heuristics for graph coloring. Computing Supplementum, 7(1990) 191-208. [100] Blas A.D., Jagota A., and Hughey R. , A range-compaction heuristic for graph coloring. Journal of Heuristics, 9(3) (2003), 489-506. [101] Lewandowski G. and Condon A., Experiments with parallel graph coloring heuristics and applications of graph coloring. vol. 26 of DIMACS Series in Discrete Mathematics and Theoretical Computer Science, (1996), 309-334. American Mathematical Society, Providence, RI, USA
[102 Fabrikant A and Hogg T, Graph coloring with quantum heuristics. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, Alberta, Canada. AAAI Press, (2002), 22-27 1103 David S. Jo R. Aragon, Lyle A. McGeoch, and Catherine Schevon Optimization by simulated ing:An experimental evaluation; part Il, graph coloring and number partitioning Operations Research, 39(3): 378-406, 1991 [104 Jagota A, An adaptive, multiple restarts neural network algorithm for graph coloring [105] Cutello V, Nicosia G, and Pavone M, A hybrid immune algorithm with information gain for the graph coloring problem. vol. 2723 of Lecture Notes in Computer Science,(2003) 171-182. Springer Verlag, Berlin, Germany [106] Glass C A. and Prugel-Bennett A, Genetic algorithms for graph colouring: Exploration of Galinier and Hao's algorithm Journal of Combinatorial Optimization, 7(3)(2003), 229-236 [107 Croitoru C, Luchian H, Gheorghies O, and Apetrei A, A new genetic graph coloring heuristic(2002), 63-74. Ithaca, New York, USA 108 Galinier P. and hac brid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4)(1999), 379-397 [) Eiben A E, Hauw J K V.D., and Hemert J.I. V, Graph coloring with adaptive evolutionary algorithms, Journal of Heuristics, 4(1)(1998), pp. 25-46 [110] Bui T.N. and Patel C M, An ant system algorithm for coloring graphs, (2002), 83-91. Ithaca, New York. USA [111]D. C. and Hertz A, Ants can colour graphs, Journal of the Operational Research Society, 48(1997),295-305 [112] Paschos V.T., Polynomial approximation and graph-coloring. Computing, 70(1)(2003), 41-86 [113 J.S. Turner. Almost all fi-colorable graphs are easy to color. Journal of algorithms, 9(1988) 63-82 [114 Ludek Kucera, Graphs with small chromatic numbers are easy to color, Information Processing Letters, 30(19 3-236 1115 Ludek Kucera, The greedy coloring is a bad probabilistic algorithm, Journal of Algorithms, 2(1991),674-684 2.求图G的色数(G)及正常x(G)点染色的算法 添边粘合法 添边、粘合操作:给定图G=(V,E),设u,v∈V(G),且t,v在G中互不相邻,则 (1)添边操作:给G添加边w,得图G’; (2)粘合操作:将uv两点粘合为一点,并去掉所得的重边,得图G
9 [102] Fabrikant A. and Hogg T., Graph coloring with quantum heuristics. In Proceedings of the Eighteenth National Conference on Artificial Intelligence and Fourteenth Conference on Innovative Applications of Artificial Intelligence, Edmonton, Alberta, Canada. AAAI Press, (2002), 22-27. [103] David S. Johnson, Cecilia R. Aragon, Lyle A. McGeoch, and Catherine Schevon. Optimization by simulated annealing: An experimental evaluation; part II, graph coloring and number partitioning. Operations Research, 39(3):378-406, 1991. [104] Jagota A., An adaptive, multiple restarts neural network algorithm for graph coloring. European Journal of Operational Research, 93(2) (1996), 257-270. [105] Cutello V., Nicosia G., and Pavone M., A hybrid immune algorithm with information gain for the graph coloring problem. vol. 2723 of Lecture Notes in Computer Science, (2003), 171-182. Springer Verlag, Berlin, Germany. [106] Glass C.A. and Prügel-Bennett A., Genetic algorithms for graph colouring: Exploration of Galinier and Hao's algorithm. Journal of Combinatorial Optimization, 7(3) (2003), 229-236. [107] Croitoru C., Luchian H., Gheorghies O., and Apetrei A., A new genetic graph coloring heuristic. (2002), 63-74. Ithaca, New York, USA. [108] Galinier P. and Hao J., Hybrid evolutionary algorithms for graph coloring. Journal of Combinatorial Optimization, 3(4) (1999), 379-397. [109] Eiben A.E., Hauw J.K.V.D., and Hemert J.I.V., Graph coloring with adaptive evolutionary algorithms, Journal of Heuristics, 4(1) (1998), pp. 25-46. [110] Bui T.N. and Patel C.M., An ant system algorithm for coloring graphs, (2002), 83-91. Ithaca, New York, USA. [111] D. C. and Hertz A., Ants can colour graphs, Journal of the Operational Research Society, 48(1997), 295-305. [112] Paschos V.T., Polynomial approximation and graph-coloring. Computing, 70(1) (2003), 41-86. [113] J. S. Turner. Almost all -colorable graphs are easy to color. Journal of Algorithms, 9(1988), 63-82. [114] Ludek Kucera, Graphs with small chromatic numbers are easy to color, Information Processing Letters, 30(1989), 233-236. [115] Ludek Kucera, The greedy coloring is a bad probabilistic algorithm, Journal of Algorithms, 12(1991), 674-684. 2. 求图 G 的色数 χ(G) 及正常 χ(G) 点染色的算法 z 添边粘合法 添边、粘合操作：给定图 G＝(V, E)，设u, v ∈V(G) ，且 u, v 在 G 中互不相邻，则 （1） 添边操作：给 G 添加边 uv，得图G′； （2） 粘合操作：将 u,v 两点粘合为一点，并去掉所得的重边，得图G′′
例如: 定理642(G)=min{(G),x(G")} 证明:考虑图G的所有可能的正常点染色方案。设l,v是G中互不相邻的两点,则在G中 的正常染色下u,v的染色有两种可能:u与v同色,或l与v异色。G的使u与v染同色 的正常点染色方案与G”的正常点染色方案一一对应,而G的使u与v染异色的正常点染色 方案与G′的正常点染色方案一一对应。因此xG)=min{(G),z(G")}。证毕。 添边粘合算法基本思想:对于给定的图G,若G是一个U阶完全图,则x(G)=U。此时给 G的每个顶点一个不同的色即可。若G不是完全图,则可取两个不相邻顶点L,v,对G进 行添边操作和粘合操作,反复进行这个过程,直至获得完全图为止。设最终得到的阶数最小 的完全图为K,则由定理642,x(G)=m。对该完全图进行顶点正常m染色,并进行反 向操作,便可得图G的顶点正常m染色。 根据定理642,添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的 执行过程是一棵二叉树,因此其计算复杂性是指数阶的。 例6.2求下图G的色数,及项点正常x(G)染色。 G 解:添边和粘合运算过程如下所示
10 例如： 定理 6.4.2 χ(G) = min{χ(G′), χ(G′′)}。 证明：考虑图 G 的所有可能的正常点染色方案。设 u, v 是 G 中互不相邻的两点，则在 G 中 的正常染色下 u, v 的染色有两种可能：u 与 v 同色，或 u 与 v 异色。G 的使 u 与 v 染同色 的正常点染色方案与G′′ 的正常点染色方案一一对应，而 G 的使 u 与 v 染异色的正常点染色 方案与G′的正常点染色方案一一对应。因此 χ(G) = min{χ(G′), χ(G′′)}。证毕。 添边粘合算法基本思想：对于给定的图 G，若 G 是一个υ 阶完全图，则 χ( ) G = υ 。此时给 G 的每个顶点一个不同的色即可。若 G 不是完全图，则可取两个不相邻顶点 u, v，对 G 进 行添边操作和粘合操作，反复进行这个过程，直至获得完全图为止。设最终得到的阶数最小 的完全图为 Km ，则由定理 6.4.2, χ(G) = m。对该完全图进行顶点正常 m 染色，并进行反 向操作，便可得图 G 的顶点正常 m 染色。 根据定理 6.4.2，添边粘合算法的运行结果是顶点染色问题的精确解。但添边粘合法的 执行过程是一棵二叉树，因此其计算复杂性是指数阶的。 例 6.4.2 求下图 G 的色数，及顶点正常 χ(G) 染色。 解：添边和粘合运算过程如下所示。 u v u v u v G G′ G′′ G G