图论着色的计数与色多项式

§6.5 染色应用举例—求图的边色数及色数的算法一、排课表问题—求二部图的正常)(G χ′边染色1. 问题： 有m 位教师m x x x ,,,21 ，n 个班级n y y y ,,,21 。

教师x i 每周需要给班级y j 上p ij 次（节）课。

要求制订一张周课时尽可能少的课程表。

2. 图论模型：构造二部图),(Y X G =，其中X ＝{m x x x ,,,21 }，Y ＝{n y y y ,,,21 }，顶点i x 与j y 之间连ij p 条边。

一个课时的安排方案对应于二部图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. 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. V ohra, 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 (log c n )-wise independence in NC. J. ACM 38 (1991), 1026–1046.3. 求二部图),(Y X G =的边正常)(G Δ染色的算法z 算法思想：给G 添加必要的顶点使得||||Y X =，再添加必要的边使得G 成为)(G Δ正则二部图，所得图记为*G ，然后反复运用匈牙利算法求*G 的完美匹配。

离散数学中的图着色与图分割离散数学是数学的一个分支，它研究的是离散的结构和对象。

在离散数学中，图论是一个非常重要的领域。

而图着色与图分割是图论中的两个基本概念。

一、图着色图着色是指给定一个图的每个顶点分配一种颜色，并且要求相邻的顶点不能有相同的颜色。

这个问题可以看作是一种涂色问题，我们希望用最少的颜色来对图的顶点进行着色。

1.1 色数与染色多项式图的色数是指给定一个图所需的最少颜色数。

一个图的色数通常用符号χ(G)表示。

图的染色多项式是对于给定的图G，它与对应的染色问题有关。

1.2 四色问题四色问题是图论中一个经典的问题，它说的是任何平面地图都可以用四种颜色进行着色，使得相邻的地图区域颜色互不相同。

这个问题虽然在1976年得到了解决，但它的证明过程非常复杂，需要运用大量的数学定理和方法。

二、图分割图分割是指将一个图分割成多个不相交的子图。

图分割在图论和组合优化中具有广泛的应用。

2.1 最小割最小割是指可以将图分割成两个不相交的子图，并且两个子图之间的边的权重之和最小。

最小割问题可以通过最大流最小割定理来解决。

2.2 图分割算法图分割算法是指用于将图分割成多个子图的算法。

常用的图分割算法包括谱图分割算法、k-means算法等。

这些算法可以根据图的特点和需求来选择合适的方法。

三、图着色与图分割的应用3.1 地图着色图着色在地图着色中有着广泛的应用。

通过给地图的每个区域进行着色，可以实现不同区域之间的边界清晰，便于观察和分析。

3.2 电路布线在电路布线中，图着色可以用于解决信号线的冲突问题，保证信号线之间不会相互干扰。

3.3 图像分割图分割在图像处理中有着重要的应用。

通过将图像分割成多个子图，可以实现目标检测、边缘提取等算法的实现。

四、总结离散数学中的图着色与图分割是图论中的两个重要概念。

图着色是将图的顶点着色的过程，目标是用尽量少的颜色进行着色。

图分割是将图分割成多个子图的过程，通过选择合适的算法可以得到满足要求的子图。

第一章 图形理论图形理论有明确的起始点，由瑞士数学家尤拉(Leonhard Euler, 1707-1783)于1736年发表的论文开始。

其研究的主要论点，乃在于解决当时的热门问题，即有名K önigsgerg 的七桥问题。

1.1 定义与例题定义1.1：令 V 为非空集合，且E V V ⊆⨯. 序对(),V E 称为(V 上)有向图(directedgraph or digraph)，其中 V 为顶点(vertex)或节点(node)的集合，E 为边(edge)的集合。

我们记(),G V E =表示此图形。

图1.1为{}, , , , V a b c d e =上有向图的例子，其中()()()(){}, , , , , , , E a a a b a d b c =。

边的方向由边上的有向箭头表示，如图所示对任意边，如(), b c ，我们说此边接合(incident)顶点, b c ；称b 邻接至(adjacent to) c ；或c 邻接自(adjacent from) b 。

此外， b 称为边的原点(origin)或源点(source)， c 称为终点(terminus or terminating vertex)。

边(), a a 为一个循环(loop)， 且顶点e 不与任何边接合，称为孤立点(isolated)。

若不考虑边的方向，此图称为无向图(undirected)。

定义1.2：令, x y 为无向图(), G V E =的顶点(不一定相异)。

G 中的X Y -路(x y -walk)是指选自G 的顶点及边的有限交错序列。

01122311,,,,,,...,,,,n n n n x x e x e x e e x e x y --==其中由顶点 1x 开始，终止于顶点y ，n 个边{}1,,1i i i e x x i n -=≤≤路的长度(length)是指该条路的边数n 。

广义Peterson图的着色问题研究张桂芝;安永红;敖特根【摘要】图的着色问题是图论的重要研究内容之一,利用广义的Pólya定理和结合一些代数方法研究了广义Peterson图在不同约束条件下的着色问题,并给出了四种不同约束条件下的色多项式.【期刊名称】《大学数学》【年(卷),期】2018(034)001【总页数】5页(P13-17)【关键词】广义Peterson图;色多项式;SC-图【作者】张桂芝;安永红;敖特根【作者单位】呼伦贝尔学院初等教育学院,内蒙古海拉尔 021008;呼伦贝尔学院数学与统计学院,内蒙古海拉尔 021008;呼伦贝尔学院科学技术处,内蒙古海拉尔021008【正文语种】中文【中图分类】O1571 引言先介绍广义Peterson图的定义.图1-1 广义Peterson图GP(8,2)定义1[1] 设三正则图G的顶点集是V={ui，vi∶0≤i≤n-1}，边集是E={vivi+1，uivi，uiui+t∶0≤i≤n-1}，其中下标取模n且n≥5，0<t<n，则称图G为广义Peterson图，记为GP(n，t). Peterson图就是GP(5，2).广义Peterson图GP(8，2)如图1-1所示.从定义容易得出以下结论：(i) GP(n，t)与GP(n，n-t)同构，即GP(n，t)≅GP(n，n-t)；(ii) (n，t)=d，则U={u0，u1，…，un-1}的导出子图G(U)是d个不相交的阶圈，称之为内圈；t≤n-12t≤n-12,(iii) 顶点集 V={v0，v1，…，vn-1}的导出子图 G(V)是一个n阶圈，称之为外圈.由(i)可知，只需研究的情形，在以后的讨论中都认为且下标均取模n.本文中主要考虑图GP(n，2)在不同约束条件下的着色方法数.定义2[2] 两个简单图G和H同构是指存在一一映射ψ∶V(G)→V(H)，且vu∈E(G)当且仅当ψ(v)ψ(u)∈E(H).从定义可知两个同构图的结构是一样的，只是顶点的标号不同而已.为了下面的结果更清楚，用以下记法.Cn，Cn′分别表示广义Peterson图GP(n，2)的外圈与内圈的n阶标号圈图，Cn的置换由两部分构成，n个旋转和n个反射构成.设(12…n)，则的元素记为其中e是的单位元.同理，设则的元素记为其中e′是的单位元.广义Peterson图GP(n，2)的点置换有2类：Cn的置换记为n个旋转和n个反射的置换记为n个旋转和n个反射所以广义Peterson图GP(n，t)的点置换：下面再介绍关于色轨道多项式的相关定义与定理.定义3[3] (i) 用Sn表示集合Nn上的对称群，即Sn是Nn上的所有置换的集合，e是Sn的单位元，且In={e}是Sn的单位子群；(ii) 若P是Sn的一个子群，则P作用在Gn上时，对任意的π∈P和g∈Gn，都有π(g)∈Gn，其边集是π(E(g))={(π(i)，π(j))∶(i，j)∈E(g)}；(iii) 当π(g)=g，即π(E(g))=E(g)时，称π是g的自同构群，g的全体自同构可构成一个群，记为A(g)；(iv) 对于任一置换π∈Sn，用C(π)表示置换π循环分解的个数，若一个置换的每个圈的长度都相等，则称此置换是正则的.定义4[3] 设P是Sn的一个子群，n阶P-置换图G或简称P-图G是指P作用在Gn上产生的一个轨道，当g∈G时，称G是g的一个P-图且g为G的一个标号图.(i) 一个Sn-图被称为是一个n阶无标号图；(ii) 一个In图被简单地看作是一个标号图；(iii) 当P=A(h)，g∈G时，其中h∈Gn，称标号图h和g分别是P-图G的结构图和约束图，由标号图h和g所确定的P-图G称为是SC-图；(iv) 当P⊆A(g)时，P-图就被称为图g的一个自同构P-图，或简称为A-图.定义5[2] 设g∈Gn，称映射σ∶V(g)→{1，2，…，k}为图g的一个正常k着色是指对任意相邻点vi和vj均满足，σ(vi)≠σ(vj).图g的一个正常k着色的最小k值称为g的色数，记为(g).对于任意的正整数k，令(g，k)表示图g的正常k着色数. 我们知道(g，k)是一个整系数的n阶多项式.从上面的定义易知引理1[3] 设g是一个标号图，π∈Sn，k是非负整数，则(i) 若π的循环节中含g的相邻顶点时，(g，π，k)=0，对所有的k≥1成立；(ii) π的循环节中均不含g的相邻顶点时，(g，π，k)(g/π，k)，其中(g/π，k)是商图g/π的色多项式.引理2[3](广义的Pólya定理) 设P是Sn的一个子群，G是g的P-图，则引理3[4] 一些特殊图的色多项式(i) (On，k)=kn；(ii) (Kn，k)=k(k-1)…(k-n+1)；(iii) (Tn，k)=k(k-1)n-1；(iv) (Cn，k)=(k-1)n+(-1)n(k-1)，其中Cn是长度为n的圈.更多关于图的染色问题的基本概念及研究结果请参见[1，2，5，6].2 广义Peterson图在不同约束条件下的着色问题定理1 设h，g∈G2n，h≅GP(n，2)，g≅K2n，令G是构造图为h，约束图为g 的SC-图，则证因为g≅K2n，所以A(g)=S2n，因此P∩A(g)=P且|P|=2n. 又因为P中除e外其余任何置换的循环节均含g的相邻顶点，所以，当π≠e时(g，π，k)=0，因此可得定理2 h，g∈G2n，h≅GP(n，2)，g≅O2n，令G是构造图为h，约束图为g的SC-图，则(i) 当n是偶数时，(ii) 当n是奇数时，证因为g≅O2n，所以A(g)=S2n，因此P∩A(g)=P且|P|=2n. 下面分情况讨论情况1 若设π0=(12…n)，π1=(1′2′…n′)，则所以存设(m，n)=d，1≤d≤n时，与的阶为所以因此这时g/π=O2d，所以(g，π，k)(O2d，k)=k2d.情况2 若记π=π′+π″，(a) 当n是偶数时，π中无循环节含g的相邻顶点，且个π使得g/π≅On，所以(g，π，k)(On，k)=kn，另外个π，使得g/π≅On+2，所以(g，π，k)(On+2，k)=kn+2；(b) 当n是奇数时，n个π使得g/π≅On+1，(g，π，k)(On+1，k)=kn+1.综上可得①当n是偶数时② 当n是奇数时定理3 设h，g∈G2n， h≅GP(n，2)， g≅nK2，E(g)={(11′)，(22′)，…，(nn′)}，令G是构造图为h，约束图为g的SC-图，则(i) 当n是偶数时，(ii) 当n是奇数时，证因为P=A(h)⊆A(g)，所以P∩A(g)=P且|P|=2n，下面分情况讨论情况1 若设π0=(12…n)，π1=(1′2′…n′)，则所以存在m∈+，使得设(m，n)=d，1≤d≤n时，与的阶为所以因此这时(g，π，k)(dK2，k)=kd(k-1)d，所以当1≤d≤n时，(g，π，k)(dK2，k)=kd(k-1)d.情况2 若记π=π′+π″，(a) 当n是偶数时，π中无循环节含g的相邻顶点，且个π使得g/π≅所以另外个π使得所以(b) 当n是奇数时，π中无循环节含g的相邻顶点，且n个π使得g/π≅综上可得① 当n是偶数时② 当n是奇数时定理4 设h，g∈G2n，h≅GP(n，2)，g≅Cn∪Cn′，即E(g)={{i，i+1}∶i∈Nn}∪{{i′，(i+2)′}∶i∈Nn}，令G是构造图为h，约束图为g的SC-图，则(i) 当(m，n)=d，2<d≤n， d是偶数时(ii) 当(m，n)=d，2<d≤n， d是奇数时证因为P=A(h)⊆A(g)，因此P∩A(g)=P且|P|=2n，下面分情况讨论情况1 若设π0=(12…n)，π1=(1′2′…n′)，则所以存在m∈+，使得当(m，n)=1时，c(π)与中均含g的相邻顶点，这时(g，π，k)=0;当(m，n)=d，2≤d≤n时，与的阶为所以因此图g/π的结构与d的奇偶性有关，所以对d进行讨论(a) 当(m，n)=d，2<d≤n且d是偶数时，g/π≅所以当d=2时，中含g的相邻顶点，这时(g，π，k)=0；(b) 当(m，n)=d，2<d≤n且d是奇数时，g/π≅2Cd，所以(g，π，k)(2Cd，k)=[(k-1)d+(-1)d(k-1)]2.情况2 若记π=π′+π″，当n是偶数时，有个π的π′中含g的相邻顶点，所以(g，π，k)=0.另外个π的π″中含g的相邻顶点，所以(g，π，k)=0.当n是奇数时，n 个π中均含g的相邻顶点，所以(g，π，k)=0.所以无论n是偶数还是奇数，都有n个π使得(g，π，k)=0.综上可得① 当(m，n)=d，2<d≤n，d是偶数时② 当(m，n)=d，2<d≤n，d是奇数时3 结论本文主要应用广义的Pólya定理和一些代数方法，对G是构造图为h，约束图为g的SC-图在以下四种不同约束条件下进行了着色方法数计算，其中h，g∈G2n，h≅GP(n，2)(Peterson图GP(n，2))，(i) g≅O2n；(ii) g≅K2n；(iii) g≅nK2，E(g)={(11′)，(22′)，…，(nn′)}；(iv) g≅Cn∪Cn′，E(g)={{i，i+1}∶i∈Nn}∪{{i′，(i+2)′}∶i∈Nn}.这些结果不仅拓展了图论中着色领域的理论结果，而且具有一定的实践应用价值.本课题研究还可进一步研究其他不同约束条件下的着色问题，其他图类的不同约束条件下的着色方法数.[参考文献]【相关文献】[1] Chris G，Gordon R. Algebraic Graph Theory[M]. New York：Springer-Verlag， 2001：112-126.[2] Bondy J A， Murty U S R. Graph Theory with Applications[M].London：The Macmillan，Press Ltd，1976： 56-66.[3] Du Q Y. Pòlya′s Formula and Chromatic Oribt Polynomials[J]. Ne i Mongolia Da Xue Xue Bao， 2000，31(16)： 551-561.[4] Biggs N L. Algebraic graph theory[M]. 2nd ed. Cambridge： Cambridge University Press， 1993： 47-48.[5] 强会英，晁福刚，等.关于扇和完全等二部图联图的点可区别边染色[J].大学数学，2009，25(4)：49-55.[6] 郝自军，张玉栋，张忠辅.关于扇和完全等二部图联图的均匀全色数[J].大学数学，2009，25(1)：35-39.。

图的边—色多项式
唐廷载;韩绍岑
【期刊名称】《数学研究与评论》
【年(卷),期】1991(011)004
【摘要】在研究图的边着色问题时,不仅要研究边着色的存在性,而且还要研究边着色的数目.为此,本文首次引入图的边-色多项式概念,并进行了初步的研究.我们认为,图的边-色多项式同图的(点)色多项式一样,是研究图的着色问题的重要工具.我们讨论的图是有限、无向且无孤立点的简单图.图G=(V,E)的一个λ-边着色π是一个映射π:E(G)→{1,
【总页数】1页(P522)
【作者】唐廷载;韩绍岑
【作者单位】不详;不详
【正文语种】中文
【中图分类】O157.5
【相关文献】
1.极大平面图的结构与着色理论（1）色多项式递推公式与四色猜想 [J], 许进
2.9阶轮图的一个派生图的色多项式唯一性的证明 [J], 李红;刘群
3.关于图色多项式系数的一个不等式 [J], 舒情;龚和林;谭海女
4.图的双变量色多项式比较研究 [J], 刘莹;唐晓清
5.Farey图及其对偶图的色多项式和流多项式 [J], 单美玲;
因版权原因，仅展示原文概要，查看原文内容请购买。