本站原创
摘要：图论最早起源于18世纪三十年代。大数学家Eulcr在1736年完成的关于哥尼斯堡七桥不足的论文,被公认为是探讨图论的开山之作。由此,Euler也被认为是图论探讨的鼻祖。伴随着图论的兴起和进展,这门新兴的学科逐渐在化学、生物学、信息论、制约论、网络论述、博弈论及计算机科学领域产生了广泛的运用。染色论述作为图论最经典的不足之一更是受到了广泛关注。由著名的“四色猜想”开始,染色论述逐步成熟和壮大,先后产生了点染色、边染色、全染色、列表染色、频道染色、条件染色等一系列新的探讨方向。在现实生活中染色论述有着广泛的运用背景,如时间表安排不足、工序不足、教室分配不足、选址不足、生产调度不足、频道分配不足等等。本论文所考虑的图都是连通的简单有限图。通常情况下,V(G),E(G)分别表示一个图G的顶点集合和边集合。|V(G)|,|E(G)|分别表示图G的顶点数和边数,有时也称为图的阶和大小。图G的一个正常k-全染色是指用k种颜色对V∪E中的元素进行着色,使得任何两个相邻接或相关联的元素获得不同的颜色。使得图G有着一个正常κ-全染色的最小正整数κ称为图G的全色数,记作χ"(G)。若只对图G的顶点(边)进行着色,则称为是图的一个点(边)染色。显然,全染色是对点染色和边染色的推广。Bchzad和Vizing分别在其论文中独立地给出了如下著名的全染色猜想。全染色猜想.对任意图G,都有χ"(G)≤△+2。尽管围绕着这个猜想已有大量的文献,该不足却至今仍未得到完全解决。本论文主要讨论两类新的染色不足,也可以称为两类标号不足,即图的[r,s,t；f]-染色及(p,1)-全标号。二者都可以看做是图的全染色的进一步推广令r,s,t是三个非负整数,,是一个定义在图G的顶点集合V上取值为正整数的函数。图G的一个[r,s,t;f]-染色即给图的每个顶点和每条边都以颜色集C={1,2,…,k}中分配一种颜色使得相邻的顶点获得的颜色差不小于r；每个顶点所关联的边满足(1)获得不同颜色的边的颜色差不小于s并且(2)获得相同颜色的边数不超过f(v)；相关联的点和边所获得的颜色差不小于t。我们把使得图有着[r,s,t;f]-染色的最小的颜色数k称为图G的[r,s,t;f]-色数,并记作Xr,s,t,f(G)。图的[r, s,t;f]-染色是我们首次提出的一个新的染色概念,它可以看作是对[r,s,t]-染色的进一步推广。[r,s,t]-染色的概念最初是由Kcmnitz和Marangio提出的。他们探讨了该染色的一些性质并用足球比赛的日程安排不足举例说明了其实际的运用价值。Kemnitz和Marangio给出了参数Xr,s,t(G)的一些上下界并针对参数r,s,t分别取一些特定值的情况得到了一系列的结果。[r,s,t]-染色是一个难度比较大的不足,即使对于星K1,。和完全图Kn等一些简单的图类也没有完全地解决。频道分配不足实质上是一个如何分配无线电频道资源以实现最合理运用的最优化不足。这个课题曾经被ATT贝尔实验室,美国国家安全局等多个机构的探讨部门所探讨。在频道分配不足中,我们需要将无线电频率(图论模型中用一些正整数代替)分配给不同的无线电接收装置。为了避开互相干扰而影响信号的传送,如果两个无线电接收装置紧挨着,则要求分配给它们的频率段至少差2,如果两个无线电接收装置靠的比较近但不是紧挨着(比如相隔一个无线电接收装置),则要求分配给它们的频率段至少差1。受这个不足的启发,RogerYch提出了L(2,1)-标号不足并很快被推广到L(p,q)-标号的形式。图的关联图是指将图G中的每条边都用一条长为2的路代替所形成的新图。Het将一个图的关联图的L(p,1)-标号不足定义为图的(p,1)-全标号不足。该不足也可以被看作是全染色不足的一种推广形式。一个图G称为是可k-(p,1)-全标号的当且仅当有着一个将V(G)∪E(G)映射到颜色集合{0,1,…,k}的函数c满足：(1)若uv∈E(G),则|c(u)—c(v)|≥1；(2)若e和e'是G的相邻边,则|c(e)—c(e,)|≥1；(3)若顶点u和边e相关联,则|c(u)—c(e)|≥p.使得G可k-(p,1)-全标号的最小的正整数k称为是图G的(p,1)-全标号数,并记作λpT(G)。本论文主要讨论图的[r,s,t;f]-染色及(p,1)-全标号。文章的主要内容及结构安排如下。第一章是绪论部分。本章的第一小节是对文中出现和用到的一些基本概念和符号的简单说明,第二小节则分别以全染色,图的[r, s,t]-染色与,-染色和频道分配不足三个方面对论文探讨内容的背景做了相对完整的介绍,接下来的第三小节则给出我们所探讨的图的[r,s,t;f]-染色及(p,1)-全标号不足的基本定义。最后,本章的第四小节将列出论文中证明的主要结论。第二章主要讨论[r,s,t；,]-染色。在这一章的第一小节中我们先对[r,s,t]-染色的一些背景和已知结果做一个简单的概括,并介绍一些在主要定理的证明中用到的符号和术语。接下来的第二小节是本章的重点部分,在这一节里我们将给出主要的结果及其证明,最后的第三小节接着给出几个可以继续探讨的不足。第三章主要讨论图的(p,1)-全标号。第一小节对(p,1)-全标号不足的起源和背景做一个简单的介绍并给出(p,1)-全标号猜想,第二小节主要介绍该不足的探讨进展和对于一些特殊图类已经取得的结果,第三小节首先给出一些在主要定理的证明历程中用到的概念和结构性引理,接下来则主要考虑与平面图相关的一些图类的(p,1)-全标号不足,以而为(p,1)-全标号猜想的成立提供新的依据。第四小节将给出关于(p,1)-全标号猜想可以进一步探讨的不足。第四章主要讨论图的列表(p,1)-全标号不足。在这一章的第一小节我们先对列表(p,1)-全标号不足做一个总体的介绍,第二小节类比列表全染色猜想给出一个关于列表(p,1)-全标号数上界的猜想,这里不妨称为弱列表(p,1)-全标号猜想,第三小节主要考虑一些特殊图类,如星、外可平面图、可嵌入欧拉示性数为ε的曲面的图等,通过证明这些特殊图类的列表(p,1)-全标号数的上界,进而为我们所提出的弱列表(p,1)-全标号猜想提供依据。最后一小节给出几个值得做进一步探讨的不足。关键词：全染色论文[r论文s论文t论文f]-染色论文(p论文1)-全标号论文平面图论文1-平面图论文
中文摘要8-12
Abstract12-17
符号说明17-19
第一章 绪论19-31
1.1 基本概念和符号19-21
1.2 背景介绍21-26
1.2.1 图的全染色21-22
1.2.2 图的[r,s,t]-染色与f-染色22-25
1.2.3 频道分配不足25-26
1.3 [r,s,t;f]-染色和(p,1)-全标号的定义26-27
1.4 主要结论27-31
第二章 图的[r,s,t;f]-染色31-43
2.1 介绍31-32
2.2 主要结果及证明32-41
2.2.1 基本结果32-36
2.2.2 min{r,s,t}=0或136-41
2.3 可进一步探讨的不足41-43
第三章 图的(p,1)-全标号43-85
3.1 背景介绍43-45
3.2 关于特殊图的基本结论45-48
3.3 主要结果的证明48-84
3.3.1 重要引理50-53
3.3.2 平面图的相关结果53-74
3.3.3 1-平面图的相关结果74-84
3.4 可进一步探讨的不足84-85
第四章 图的列表(p,1)-全标号85-101
4.1 介绍85-86
4.2 弱列表(p,1)-全标号猜想86-88
4.3 主要定理及证明88-100
4.3.1 星图的相关结果88-90
4.3.2 外可平面图的相关结果90-97
4.3.3 平面图的相关结果97-100
4.4 可进一步探讨的不足100-101