图上几类边覆盖染色问题的研究

论文摘要

图论的研究已经有二百多年的历史,早在1736年Eulcr就用图论方法解决了著名的哥尼斯堡七桥问题。随着现代生产和科学技术的发展,图论方法得到了广泛的应用,使图论成为现代数学科学中的重要学科。由四色猜想诱导出来的图的染色理论在图论研究中占有重要的地位。目前,图的染色理论已成为图论中的一个重要分支,它在计算机理论、最优化、网络设计等方面都有着重要的应用,例如在Hcssians矩阵的计算、网络中的数据传输等方面。图的染色问题有很多,诸如边染色、点染色、面染色和全染色问题等,其中最基本的染色问题之一就是图的边染色。图的正常边染色就是把图的边集分解为一些互不相交的边独立集的并的方法。在图的正常边染色理论中有著名的Vizing定理,而其中图关于正常边染色的分类问题一直是研究的热点之一。近年来,人们开始考虑把图的边集分解为其它形式,得到一些新的边染色问题并进行研究。本文主要讨论了图的边覆盖染色、f-边覆盖染色、分数f-边覆盖染色等。我们用G（V（G）,E（G））表示一个图,其中V（G）是图G的顶点集,E（G）是图G的边集。假设S是一个集合,用|S|表示集合S的基数。如果图G中不允许出现重边和环则称G为简单图,如果图G中允许出现重边但不允许出现环则称G为多重图,在本文中,如果没有特别说明,我们所说的图是指简单图。对图G中的点v,用dG（v）表示顶点v的度,用NG（v）表示v的邻点集。我们用δ（G）和△（G）分别表示图G的最小度和最大度,即δ（G）=min{dG（v）:u∈V（G）},Δ（G）=max{dG（v）:v∈V（G）}不致产生混淆时,我们用V,E,N（v）,δ,△分别代替V（G）,E（G）,NG（v）,δ（G）,Δ（G）.如果图G满足Δ（G）=δ（G）=d,则称图G是d-正则图,3-正则图通常被称为立方图。如果图G的顶点集可以划分为两个互不相交的子集V1和V2,且G的任意一条边关联的两个端点分别在V1和V2中,则称图G为二部图。若图G中存在一点u使得G-u是一个具有二划分为（X,Y）的二部图,则称G为近似二部图,记为G（X,Y;u）.如果G（V,E）是图G1（V1,E1）和图G2（V2,E2）的完全并（图G1和图G2没有公共顶点）,即V=V1∪V2并且E=E1∪E2∪{uv:u∈V1,v∈V2},则称图G（V,E）是连结图。假定对V（G）中每个顶点v,都用一个正整数f（v）给以赋值,且要求1≤f（v）≤d（v）我们用正整数1,2,…,κ来表示颜色,如果C是边集E（G）到集合{1,2,…,κ}的映射,则称C为图G的κ-边染色。我们用ci（v）表示在染色C中与顶点v关联的染颜色i的边的数目。如果染色C满足对图G中每个顶点v∈V和每种颜色i∈{1,2,…,κ},都有ci（v）≥f（v）成立,则称C为图G的f-边覆盖染色。能对图G进行f-边覆盖染色所使用的颜色的最大数目,称为图G的f-边覆盖色数,记为Xfc’（G）令δf=v∈Vmin{（?）d（v）/f（v）（?）}其中（?）d（v）/f（v）（?）是指不大于d（v）/f（v）的最大整数。已知δf-1≤Xfc’（G）≤δf.由上面的式子知,图G的f-边覆盖色数Xfc’（G）要么等于δf-1,要么等于δf,由此我们根据Xfc’（G）把图分为两大类：若Xfc’（G）=δ,则称G是fc-1类的,否则称G是fc-2类的。如果对所有的顶点v,都有f（v）=1,则有δf=δ,此时图G的f-边覆盖染色就退化为通一般意义上的边覆盖染色。能够对图G进行边覆盖染色所需的最大颜色数,称为图G的边覆盖色数,记为Xc’（G）.类似的,图关于边覆盖染色也可以进行分类,即若Xc’（G）=δ则称G是C1类的,否则称G是C2类的。对于正则图来说,其关于边覆盖染色的分类问题等价于其关于正常边染色的分类问题。因此,图关于边覆盖染色的分类问题也是NP-完全的。对任意的图讨论它关于边覆盖染色的分类问题是非常困难的,但对一些特殊的图类讨论其分类问题是可能的。我们知道,在讨论图的分类问题时,“临界”是一个非常重要的概念。如果图G是连通的非完全图且满足χ’fc（G）=δf-1,且对任意的u,v∈V, e=uv（?）E都有χ’fc（G+e）=δf成立,则称图G是f-边覆盖临界的。如果对所有的顶点v取f（v）=1,则相应的有边覆盖临界图的概念。研究f-边覆盖临界图的性质对于解决图的关于f-边覆盖染色的分类问题具有重要意义。分数图论是图论的一个重要分支。图的分数边染色和分数边覆盖染色都是一些相对较新的研究方向,他们分别对讨论图的正常边染色和边覆盖染色有十分重要的作用。在本文中我们首次提出了图的分数f-边覆盖染色的概念,它对讨论图的f-边覆盖染色问题同样也有重要的作用。因此,讨论图的分数f-边覆盖染色也是非常有意义的。图G的分数f-边覆盖染色是指给G的每一个f-边覆盖F分配非负权ωF,使得对任意的e∈E（G）满足∑F（?）eωF≤1,其中∑F∈e是对含边e的G的所有的f-边覆盖求和。图G的分数f-边覆盖色数Xfcf’（G）是指可以对图G进行分数f-边覆盖染色,且使∑FωF取最大值,其中求和是对G的所有的f-边覆盖F进行。图的边覆盖染色问题与图的正常边染色问题有很多对应的结论,但其本质上有很大的不同,边覆盖染色的大多数结论无法从正常边染色的结论中直接推出来。对这两类问题进行研究的思路和方法是完全不同的,边覆盖染色研究的难度是非常大的。本文主要考虑图的几类染色问题。我们主要讨论图的边覆盖染色、f-边覆盖染色、分数f-边覆盖染色等。本文分四章进行讨论。在第一章,我们首先介绍一些用到的基本概念和定义。然后给出有关的染色的定义和研究历史并给出了本文的主要结果。在第二章,我们讨论了边覆盖染色的分类。首先给出了一般图是C1类图或C2类图的一些充分条件,给出了一种构造边覆盖临界图的方法,然后对某些特殊图的分类进行了讨论,并得到了一些新结果。在第三章,我们首先对f-边覆盖染色的分类进行了研究,得到了有关正则图和近似二部图的一些结果,然后对f-边覆盖临界图的性质进行了研究,得到了许多比一般的边覆盖染色更强的结果。在第四章,我们介绍了分数f-边覆盖色数的定义并给出了一个更为精确的分数f-边覆盖色数的计算公式。令和则我们有它对于图的f-边覆盖染色的分类有重要意义。

论文目录

• 中文摘要
• 英文摘要
• 符号说明
• 第一章 绪论
• 1.1 基本定义和符号
• 1.2 图的边染色的历史和发展
• 1.2.1 图的边覆盖染色
• 1.2.2 图的f-边覆盖染色
• 1.2.3 图的分数f-边覆盖染色
• 1.3 主要结果
• 第二章 图的边覆盖染色
• 2.1 简介
• 2.2 预备知识
• 2.3 图的边覆盖染色
• 2.4 连结图的边覆盖染色
• 2.5 进一步要考虑的问题
• 第三章 图的f-边覆盖染色
• 3.1 简介
• 3.2 图关于f-边覆盖染色的分类
• 3.3 正则图的f-边覆盖染色
• 3.4 近似二部图的f-边覆盖染色
• 3.5 f-边覆盖临界图的性质
• 3.6 进一步要考虑的问题
• 第四章 多重图的分数f-边覆盖染色
• 4.1 简介
• 4.2 预备知识
• 4.3 主要结果
• 参考文献
• 致谢
• 作者简介
• 学位论文评阅及答辩情况表