§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-3291 §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