稀疏平面图的(3,0)-染色.docx

《稀疏平面图的(3,0)-染色.docx》由会员分享，可在线阅读，更多相关《稀疏平面图的(3,0)-染色.docx（10页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、一、引言图论作为数学领域的一个重要分支，它既有历史沉淀的传统厚重性，又有与新时代新科技相结合的时代前沿性，不仅对现实生产生活有着非常实用的价值，也对先进科学方面有着举足轻重的作用。在我们日常生产生活中，图的染色问题的理论早已渗入其中。例如：任务的分配问题、邮路的最短行程问题、电路的布局问题、化学物品的存放问题、企业物资与工作流程的安排问题等等，我们都可以将这些实际问题转化为图的染色问题，利用图的相关知识来解决实际问题。图的染色的理论在科学技术方面的应用是非常广泛的，它在诸如运筹学、控制论、网络设计理论、网络最优化、组合最优化等方面都占有一席之地。顾名思义，图是图论的主要研究对象。在图中，我们将

2、研究对象分为两类，一类是图中的点，另一类就是图中的边。对于点来说，表示的就是特定对象；对于边来说，表示两个点之间某种特定的关系，在实际问题中通常表现为利益、流量、物资、距离、重量等等。被人们所熟知的“哥尼斯堡七桥问题”是图论历史上可考的最早文字的记载。在瑞士数学家欧拉给予该问题解决策略之后，一个全新的数学领域诞生，就是我们今天所说的图论。再到后来，图论历史中的一个非常重大的事件横空出世历史上第一部图论的专著有限图与无限图理论诞生。在此之后，经历了几百年的艰难曲折的发展，图论领域不断扩展，变得更加系统，变得更加科学，经历了两次大的繁荣之后，图论这棵大树上也开始瓜果飘香、硕果累累。在图论的产生和发

3、展经历了近三百年的历史长河中，我们大致上可以将其分为以下三个不同的阶段: 阶段一：从欧拉解决“哥尼斯堡七桥问题”到开始19世纪50年代，当时研究的图论问题还比较简单，比较生活化，大部分来源于生活问题和游戏问题。 阶段二：从19世纪50年代到1936年，受到西方博弈论的影响，图论主要研究的问题就变成了一些博弈类问题。在这个时期内，图论这棵大树开始变得繁荣，一些著名问题都踊跃而出，如四色问题和环游问题等。图论的发展到了一个第一个繁荣时期。在这个时期内，图论领域开始逐渐向其他领域发展，其中效果最突出的要数德国的数学家克希霍夫和英国的数学家凯勒。此二人极大的拓展了图论的应用领域，为后续学者们提供了拓展

4、的先例，为图论的继续发展奠定了基础。 阶段三：就是从1936年至今，由于科学技术的进一步发展，现实生活和科学技术领域遇到的困难日益增多，仅仅依靠人力是不可能承担如此繁杂的工作，正是由于1936年计算机的诞生，使得运算的速度和可运算的工作量大幅度提高，提高的运算的效率，极大的减轻了人的计算量。在计算机的帮助，同时大量地分析其中的问题所涉及到的复杂图形才有了可能，从而将人从冗杂的计算中脱离出来，研究更有价值的问题。在计算机的出现和帮助下，图论的发展突飞猛进，与其他领域融合的更加紧密，图论的发展到达了第二个繁荣时期。根据染色对象的不同，图的染色可以分成两种：图的点染色和图的边染色。本文中，我们考虑平

5、面图的点染色。平面图就是图中所有的点都在同一平面内，并且使得边与边仅在顶点处相交的图。平面图的点染色就是对平面图中的每一个点按规则进行着色。对于平面图来说，我们可利用图中同一条边的相邻两个点之间的关系将图分为无向图和有向图。我们知道图中的每一条边ek都有与之关联的两个点vi和vj。对于无向图来说，两个点的次序对这条边没有任何影响，即ek=vi，vj=vj，vi；而对于有向图来说边ei，j=vi，vj和边ej，i=vj，vi表示的便不是同一条边了，两个端点对应相同的两条边称为平行边。特别的，如果存在这样的边ek=vi，vi，即这条边的起点就是这条边的终点，我们称这样的边为环。一个图如果满足没有平

6、行边和环，我们称之为简单图。本文，我们所研究的就是简单图的点染色问题。在图中，我们称相邻的两个点距离为1，如果不相邻的两点若有公共邻点，则称其距离为2。在图中，如果点v恰邻接k个点，那么我们称点v为k度点，记作dv=k。而对于整个图G来说，最大的k值被称为图G的最大度，记为。在图中，如果一个点没有与之相邻的顶点，我们称之为独立点；如果一个点有且只有一个邻点，我们称之为悬挂点，该悬挂点与其邻点之间的所关联的边，我们称之为悬挂边。设G=V，E表示一个平面图。如果存在一个映射：V 1,2,.,k，其中对于任意的k都有kZ+，如果满足对任意ab E，有（a）（b），我们则称映射是G的一个正常k-染色，

7、与此同时，我们称平面图G是正常k-可染的。如果我们用V1，V2,，V3，.，Vk来表示图G中染相同颜色的顶点，使之成为图G的一个剖分，使得由Vi的点导出子图G Vi最大度不超过di，其中 1ik，则称图G是（d1，d2，.，dk）-可染的。此定义包含了正常的k染色（即d1=d2=d3 =.= dk= 0时）和放松的k染色（ 1ik, 使得di1时）的两个概念。设序列W=v0e1v1e2v2ekvk是图G的一个有限非空列，我们则称序列W为图G的一条径；其中W满足 如果它是由顶点和边交替出现而构成的 并能使得对于任意1ik，ei的端点为vi和vi-1。满足各顶点互不相同的径W，是图G的一条路；满足

8、各边互不相同的径W是图G的一条链。如果满足一条径（链或路）起点和终点是重合的并且长度是正的，则之为闭径（链或路）。圈是闭链的一种特殊情况，即圈是满足起点与闭链上的剩余点互不相同的闭链，并且规定长度为n的圈称为n圈。任何一个平面图都是（0,0,0,0）-可染的1,2（即四色定理）和（2,2,2）-可染的13。平面图（2,2,2）-可染这个结果是最好的（因为对于任何整数k，都存在非（k，k，1）-可染的平面图的例子15,20）。而对于图的3-可染，我们这里给出(0,0,0)-染色的最新进展：任满足一下任意一个条件的平面图都是(0,0,0)-可染的： 无3的圈的平面图。21 无4圈、5圈、6圈和7圈

9、的平面图。22 无4圈、5圈、6圈和8圈的平面图。23 无4圈、5圈、6圈和9圈的平面图。24 无4圈、5圈、7圈和8的平面图都。25 无4圈、5圈、7圈和9圈的平面图。26 无4圈、5圈、8圈和9圈的平面图。27 无4圈、6圈、7圈和8圈的平面图。28 无4圈、6圈、7圈和9圈的平面图。29 无4圈、6圈、8圈和9圈的平面图。30 无4圈、7圈、8圈和9圈的平面图。31 无4圈、5圈和7圈的平面图。32 无4圈、6圈和8圈的平面图。33 无4圈、7圈和9圈的平面图。34因为平面图3-染色已经得到较好的解决，所以平面图的放松染色问题目前就集中在(d1，d2)-染色上面。图G的围长是G中最小圈的

10、长度,用g(G)表示；图G的最大平均度是图G的各个子图的平均度的最大值，用mad（G）表示，即madG=max2|EH|VH|,HG。我们一般用最大平均度mad（G）来表示图的稠密程度。如果图G的最大平均度是一个常数,那我们则称G是稀疏图。下面我们就针对图的最大平均度和围长两个方面对图进行深入讨论，简略的分类列出关于（d1，d2）-染色的最新成果。 （1,0）-染色当围长至少为16时，Glebov和Zambalaeva17证明了此类平面图都是（1,0）-可染的。Borodin和Ivanova3优化了该结果，减小了（1，0）-可染的最小围长，他们证明满足mad(G)73的任意平面图G都是（1，0

11、）-可染的，这意味着任何一个围长至少为14的平面图G都是（1，0）-可染的。随后，Borodin和Kostochka7从最大平均度的角度出发，给出了满足mad(G)125的每一个平面图G都是（1，0）-可染的证明,这也就意味着对于每个围长至少为12的平面图都是（1，0）-可染的。另一方面，Borodin和Kostochka7还从反面角度构造出了满足当平面图的最大平均度从上方无限逼近12/5时，存在非（1，0）-染色的例子的平面图。由此可知，（1，0）-染色问题在最大平均度上的上述结果几乎是最优的。紧接着，Kim，Kostochka和Zhu19从无三圈平面图的角度继续考虑(1,0)-染色问题，他

12、们证明围长至少为11的平面图是(1,0)-可染的。早在2013年，Esperet，Montassier，Ochem和Pinlou16就已经证明围长是9的平面图的(1,0)-可染问题是NP完全问题。而围长是10的平面图是否(1,0)-可染这个问题仍然没有得到解决。（k，0）-染色（k2）在Borodin和Ivanova3给出了任何一个围长至少是14的平面图G都是（1,0）-可染的结论的基础上，Borodin，Ivanova，Montassier，Ochem和Raspaud 4扩展了其结果，从最大平均度的角度给出了满足mad(G)3k+4k+2的任何一个平面图G都是（k，0）-可染的。随后，Bor

13、odin和Kostochka 8给出了围长与最大平均度对于染色的关系，对于正整数k2，满足mad(G)3k+2k+1的任意一个平面图G是（k，0）-可染的证明。就最大平均度而言，这个结果是紧的。 另一方面，Montassier和Ochem10证明了围长至少是7的平面图的存在非(2,0)-可染的例子，并提出了一个问题：围长至少是7的平面图是否是(3,0)-可染的。（k，j）-染色从最大平均度的角度出发，Borodin，Kostochka和Yancey 9证明了每一个满足mad(G)145的图都是（1,1）-可染的；Borodin，Ivanova, Montassier和 Raspaud5，证明了

14、对于任意的k2，每一个满足mad(G)10k+223k+9的图G都是（k，1）-可染的。Havet和Sereni 18从最大平均度的角度出发，证明对于任一个k0，任何一个满足mad(G)4k+4k+2的图G都是（k，k）-可染的（在这里实际上是（k ，k）-可选的）。Borodin，Ivanova，Montassier和Raspaud 6根据平面图的密度，给出了（k，j）-可染的一些充分性条件。最后，Borodin和Kostochka 8证明：对j0且k2j+2，每一个满足mad(G)2(2-k+2(j+2)(k+1)的图G都是（k，j）-是可染的。就最大平均度而言，这个结果是严格的，并改进了

15、4，5，6中的某些结果。我们知道，利用任何平面图G满足mad(G)2G(G)GG-2这一事实，最大平均度条件的相关结果就可推出相应围长平面图的结果。表1中给出了基于围长条件平面图(k,j)-染色的最新进展。围长(k,0)(k,1)(k,2)(k,3)(k,4)3,45(10,1)11(6,2)8(4,3)12(3,4)126(4,1)8(2,2)187(4,0)8(1,1)98(2,0)811(1,0)19表1.平面图的围长和（k，j）-染色情况。注：符号“”表示对于该围长和对应的整数k，存在非（k，j）-染色的例子。二、主要结果Borodin和Kostochka 8得到了下列结果：定理18

16、围长至少为8的平面图是(2,0)-可染的。定理28 围长至少为7的平面图的(4,0)-可染的。Montassier和Ochem10证明了围长为7的平面图的存在非(2,0)-可染的例子。本文讨论围长至少为7的平面图的(3,0)-可染性问题，我们证明下列结论：定理3设G是围长为7的平面图，用M(G)记G所有7圈上度不超过4的点的集合。若G每个七圈上都含有M(G)中的点，且每个度数至少为5的点最多邻接一个 M(G)中的点，则图G是（3，0）-可染的。我们的证明思路是先删掉M(G)中的点，得到一个围长至少为8的平面图G=G-M(G)。由定理1，得到G的一个(2,0)-染色，从而得到G的一个部分的(2，

17、0)-染色。基于该染色，对M(G)中的点进行染色，扩充得到G的一个(3,0)-染色。我们用两种颜色b和0来对平面图G进行点染色，使得染0色的点形成独立集，通过以下几个引理的证明来完成定理3的证明。引理1 图G- M(G)是(2,0)-可染的。引理2 基于G- M(G)的任一个(2,0)-染色，可以得到G的一个点染色，使得点染色满足下列条件：(1) 对任意的点vVG-MG，v=v ；(2) 对任一点uMG，若u=0，则u的所有邻点染颜色b，若u=b，则u至少有一个邻点染颜色0；(3) 染色中染颜色0的所有点是G的一个独立集。引理3必要时将VG-MG中部分染颜色b的且度数不超过4的点改染为颜色0，

18、即可由染色得到G的一个(3,0)-染色。三、结果证明 3.1引理1证明引理1 图G- M(G)是(2,0)-可染的。证明：由M(G)的定义我们可知，M(G)是G所有7圈上度不超过4的点的集合，并且每一个7圈上都包含有M(G)中的点。对于围长至少是7的平面图G来说，图G-M(G)就意味着从图G中将点集M(G)中的点删掉，破坏掉所有的7圈，这样我们就得到了一个围长至少是8的图G=G-M(G)。由定理1我们可知，围长至少是8的平面图G是(2,0)-可染的。引理1得证。3.2 引理2证明引理2 基于G- M(G)的任一个(2,0)-染色，可以得到G的一个点染色，使得点染色满足下列条件：对任意的点vVG

19、-MG，v=v ； 对任一点uMG, 若u=0, 则u的所有邻点染颜色b，若u=b, 则u至少有一个邻点染颜色0；染色中染颜色0的所有点是G的一个独立集。证明：在引理1中，我们得知图G=G-M(G)是(2,0)-可染的，我们将这种染色记为染色，在染色的基础上，我们再对M(G)中的点进行染色，得到图G的一个染色。我们给出染色规则如下：前提：由引理1可知，图G- M(G)是围长至少是8的平面图，所以我们先给出图G- M(G)的一个(2,0)-染色；染色：接下来我们再去考虑M(G)，我们任选M(G)中的一个点v，对该点进行着色，着色规则如下：若该点相邻的点的颜色都是b，则该点染颜色0；否则就染颜色b

20、。 集：从点集M(G)中删掉点v。 循环：重复步，直至点集M(G)为空集。这样来看，图G中的所有点都有颜色可染，而上述染色过程的第步恰好满足证明条件第步vVG-MG，v=v，即从图G染色，通过M(G)，扩充到了G的一个染色；染色过程的第步正好满足证明条件的第步对任一点uMG, 若u=0, 则u的所有邻点染颜色b，若u=b, 则u至少有一个邻点染颜色0，这样就使得在染色过程中不会出现两个染0颜色的点相邻，也不会出现染颜色b的点相邻4个染颜色b的点；而染色过程的第步又恰好印证了证明条件里的第步染色中染颜色0的所有点是G的独立集，由于这是一个循环染色，每一次循环都能够确保证明条件是能够满足的，在有限

21、此循环之后，证明条件也必然能够满足，所以染色中染颜色0的所有点是G的一个独立集。证毕。我们接下来考虑，在G中，G与M(G)距离为1的度数不超过4 的点在染色中染色的情况，该情况下该点可以最多邻接M(G)中的4个点。我们还要考虑，在G中，G与M(G)距离为1的度数至少为5的点在染色中染色的情况。在G的染色中，每个染颜色b的点至多邻接2个b色邻点，染颜色0的点集是独立集。在G的染色中，染颜色0的点集是独立集；M(G)中染颜色b的点至多邻接3个b色邻点；但V(G)M(G)中的染颜色b的点可能邻接多于3个b色点。如何去处理这些问题呢，我们将会在引理3中来解决。3.3 引理3证明引理3必要时将VG-MG

22、中部分染颜色b的且度数不超过4的点改染为颜色0，即可由染色得到G的一个(3,0)-染色。证明：由引理2的证明中我们知道，在给出图G的染色之后就会出现问题。我们先考虑染颜色0的点，由引理2我们知道图G的染色中的所有染颜色0的点是G的1个独立集，因此染颜色0的点不会出现问题。接着我们再来考虑染颜色b的点，由引理2可知，M（G）染颜色b的点至多会邻接3个染颜色b的点，这是符合我们染色要求的；而V（G）-M（G）中染颜色b的点就是我们问题所在，我们把这些出现问题的点称之为“违规点”。当V（G）-M（G）中染颜色b的点是度数不小于5的点时，是不会出现问题的，因为该点至多会邻接M（G）中的1个点，所以该点

23、在染色扩充至染色时至多会增加1个染颜色b的邻点，即该点至多有3个染颜色b的邻点，是符合我们的染色要求的；当V（G）-M（G）中的b色点是度数不超过4的点时，该点就有可能出现邻接4个染颜色b的点，这就不符合我们的染色要求，因为该“违规点”是度数不超过4的点，我们只需要将该点的颜色由b换成0即可，这样我们就在对染色调整的基础上，可以得到一个G的一个（3，0）-染色了。引理3得证。3.4定理3证明证明：对围长是7，每个7圈上都含有M（G）中的点，且每个度数不小于5的点至多邻接M（G）中的1个点的平面图G进行染色，根据引理1，用颜色b和颜色0对图G进行染色，并给出G一个（2，0）-染色，然后根据引理2，依次对M(G)中的点进行染色，得到了图G的一个（3，0）-染色。如果染色不是G的(3,0)-染色，根据引理3，将出现问题的“违规点”由颜色b染成颜色0即可。所以，由这三个引理我们可以得出，若G每个七圈上都含有M(G)中的点，且每个度数至少为5的点最多邻接一个 M(G)中的点，则图G是（3，0）-可染的。定理3得证。