图论和其应用对图均匀染色探究

《图论和其应用对图均匀染色探究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、图论和其应用对图均匀染色探究　　摘要对于图论研究而言，图的染色问题既是重点，又是热点。本文将围绕图的均匀染色问题展开相关探究，先后讨论了平面图的均匀染色、2-退化图的均匀染色以及图的全染色等。关键词图论均匀染色全染色中图分类号：O157文献标识码：A1均匀染色概述对于图论研究而言，图的染色问题既是重点，又是热点。图的均匀染色属于一种相对特殊的图的染色问题，自诞生以来，在以工业生产的代表的诸多领域获得了广泛应用，在处理时间表问题、剖分问题以及承载平衡问题等方面发挥出了相当重要的作用。如进行工作安排时，同一个时间段内所要开展的工作将会受限于操作人员的数量。上述对色

2、类大小的约束便促进了图的有界染色问题的提出和发展。对于图而言，假设为其某个正常状态下的顶点染色，若要求在下，无论哪一个色类中的顶点数均不可超过，那么可将6当成是图的一个所谓的-界染色。若想予以强化，对每两个色类提出更高的要求，要求它们的顶点数差值必须控制在1以内，如此一来，便形成了本文所要探讨的图的均匀染色问题。很明显，对于图的一个均匀染色而言，也可将其当作图的一个[∣（）∣/]-界染色。①图的均匀染色，其特殊之处在于：k-可对图进行均匀染色，然而（k+1）-并非百分百具有这个性质。2图的均匀染色2.1平面图的均匀染色设图属于平面图，人们习惯用（）来代表面的集

3、合，在保证不会造成混淆的前提下，用表示（），并将其称之为面，且和周界上的诸点存在关联。所谓面的度数（）指的是，和其存在关联关系的边的条数，其中，割边将会被计算2次。如果面的边界以一个圈的形态存在，那么该面被称之为简单面。在∈（）的情况下，习惯用（）来代表面的闭途径，与此同时，用（）来代表和面存在关联关系的顶点集。如果b（）包含的各个顶点依次表示为，，…，，那么可记=（…）。②如果平面的所有顶点均位于同一个没有界面的边界上，那么则被称之为外平面图。③对平面图的均匀染色进行研究时，王维凡等人针对如下问题进行了研究：当△（）赋值为5时，平面图的边列表染色将不涉及4-

4、圈或者6-圈。从中可获得相应的启发，即对不涉及短圈的平面图的均匀染色这一类问题予以探究。6相关定理有：（1）每个不含5-圈的平面图均是由3-退化而来的；（2）若平面图不含3-圈、4-圈以及5-圈，那么对于任何一个≥{4，△（）}而言，存在一个-均匀染色；（3）每个不含6-圈的平面图均是由3-退化得到的。2.22-退化图的均匀染色以如下定理及其证明为例。定理：将（）的一个顶点记作，假设={，，…，}为的子集，同时符合∣（）∣≤（1≤≤），当满足-包含-均匀染色这一条件时，便能够得出也包含-均匀染色。④证明：令=，同时令=[（）∪{}]（1≤≤），那么可得出、相等

5、。将当作是包含的一个-均匀染色，此时色集可表示为={1，2，…，}。由于∣（）∣≤，那么将必然有这样一种颜色，能够使条件下的不和上述染色（即）的顶点保持相邻关系，此时，用完成的染色，则能够对的产生一个延拓效果，得到下的。考虑到∣（）∣≤，那么必然有一种以上的颜色∈{}，能够让条件下的不和的顶点保持相邻关系，接下来，用完成完成的染色，则能够对的产生一个延拓效果，得到下的。按照上述规则进行下去，直至将所涉及的诸多顶点全部赋予一种颜色，如此一来，便能够获得的一个所谓的-正常染色。很明显，对于所涉及的个顶点而言，各自所染颜色全部存在差异，如此可证明为的一个所谓的-均匀

6、染色。3图的均匀全染色3.1一类Mycielski图的均匀全色数以如下定理及其证明为例。6定理：对+1阶星而言，可以得到如下结论（（））=△（（））+1（≥2）。证明：由于△（（））=2，那么可知（（））≥2+1。现在仅需要对以下问题进行验证，即存在（（））的一个2+1-均匀全染色，并将其定义为图：（）=（（））∪{}，（）=（（（））/{}）∪{∣=0，2，3，...，}∪{，∣=0，3，4，...，}∪{}。可得△（）={，}，另外，G*中所具有的最大度点的导出图（即[△]=）属于一条路，如此一来，可以得出：（）=△（）=2，那么对于而言，存在一个2-均匀

7、边染色，假设属于的一个2-均匀边染色，那么在这一条件的基础上，便可构造（）的一个点边全染色，记为，则有：（）=（），=0，2，3，…，；（）=（），=0，3，4，…，；（）=（）=（）=（）=2+1；（）=（）；（）=（），∈（（））/{}。很容易得出属于（）的一个点边全染色，同时∈{1，2，…，2+1}，另外，∣∣=3或者4。⑤所以，可以得出属于（）的一个2+1-均匀全染色。最终证得：（（））=△（（））+1。3.2一些特殊平面图的均匀全色数以平面图圈为研究对象，对其点边面均匀全染色问题予以研究。定理：对圈（）（≥3），如果=∣∣，那么可以得出（）=+2。6

8、证明：对圈，假设其顶点分别是，，…，，