董桂香[1]2003年在《关于若干图类的着色问题》文中研究表明本文讨论了若干图类的四种不同的着色问题：动态着色、关联着色、平面图的完备着色和边面着色。利用构造性组合方法和换色技巧给出了Halin图和系列平行图动态色数的最小上界，并确定了一类特殊系列平行图的动态色数，确定了某些笛卡儿积图和某些联图的关联色数，确定了1-树图的完备色数并证明了有关边面着色的一个猜想。
陈亮[2]2007年在《图的全染色以及邻点可区别全染色》文中研究指明具有重要的理论意义和实用价值的各种染色问题,一直是图论中的热点话题之一。离散系统、组合分析中的许多问题都可转化为图着色问题,例如,不含给定图G作为子图的n个顶点的图的边的最大数目就依赖于G的色数。因此T R.Jensen和B.Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关,也正是图着色理论的实际应用才引起了世人的兴趣。所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色,继图的点着色、边着色以及组合地图的面着色之后,人们又提出了全色数的概念。如点着色、边着色、全着色、强染色、邻强边着色、邻点可区别全染色、点可区别边染色、边面着色、完美着色等成百上千种着色方式。为了恰当地表示大型超网络、存储问题、时间安排和任务分配等研究课题中各元素之间的关系,图的染色理论做为一种可行的工具被自然的引入。由于其良好的应用背景,图的染色理论已成为现在图论领域中迅速发展的子学科之一。本论文首先综述了全染色的基本概念和研究现状,然后统一各种文献中有关染色的概念。文章根据全着色理论得出了若干图的全色数,并通过对这些图的全色数的确定验证全着色猜想(TCC),得出了全着色方面的一些定理,在全着色的实际应用中,给出了某些图的全着色算法。其次,文章引入邻点可区别全着色,邻点可区别全着色是全着色理论的一个最新研究方向,张忠辅等人提出图的邻点可区别全着色这个概念,得到了若干结果,并提出了有关猜想,目前所知结果甚少,尚有许多未解决的问题,邻点可区别全着色理论是本文的研究重点,给出了几类图的邻点可区别全色数,验证了邻点可区别全着色猜想。
许振宇[3]2003年在《若干图着色问题的研究》文中研究说明本文研究了叁种不同的着色：图的关联着色、无圈边着色和强边着色。分别确定树和3k-圈的膨胀图及圈、K_(2.n)、扇图和△≥6的Halin图的一致膨胀图的关联色数。证明了Halin图、1-树和外平面图满足由N.Alon提出的任何一个图的无圈边色数不超过其最大度加2的猜想。给出了两类高度正则图的强边色数，并对A.C.Burris的一个结果进行了初步的探讨。
戴本球[4]2015年在《图的放松的距离二标号着色》文中研究表明标号着色是从频道分配问题中抽象出来的一种图着色概念。与经典的图着色相比,它不仅要求图中相邻元素的着色有着明显的差别,同时还要求图中不相邻元素的着色有所不同。图G的距离二标号着色也即L(j,k)-标号,有整数距离二标号(j,k为非负整数)和实数距离二标号(j,k为非负实数)两种模式。它们分别是定义在V(G)→{0,1,2,3,…}和V(G)→[0,+∞)上的函数f,满足条件：(1)|f(u)-f(v)|≥j,若uv∈E(G)；(2) |f(u)-f(v)|≥k,若d(u,v)=2。图G的L(j,k)-标号着色数λj,k(G)=minf max{f(v): v∈V(G)}。随着图着色问题研究的不断深入,各种各样的图着色的变形和推广出现并被广泛研究,诸如有缺陷着色、非正常着色、荫度等等,它们都可看作是对图的正常着色的放松。着色放松问题实际上还有很多问题值得深入挖掘和思考。标号着色的放松问题在理论上就值得研究,同时它也有实际应用价值。为解决频道分配问题,需要选取合适的数学模型,合理地分配稀缺并且有限的频道资源。放松的距离二标号着色是更为合适的频道分配问题的数学模型。假设G是一个图,f：V(G)→{0,1,2，...]是一个映射,s,t是两个非负整数。若对于G的任何两个相邻顶点u,v,f(u)≠f(v)；对于G的任何顶点u,至多有s个u的邻点标号属于集合{f(u)-1,(u)+1},至多有t个u的2-邻点的标号等于f(u),则称f是图G的(s,t)-放松的L(2,1)-标号。记f的跨度为span(f),表示图中顶点的最大标号和最小标号的差。图的(s,t)-放松的L(2,1)-标号的最小跨度定义为图的(s,t)-放松的L(2,1)-标号着色数,记为λ2,1s,t(G)。图的(s,t)-放松的L(2,1)-标号是对图的整数L(2,1)-标号作出相应的放松而产生的新的图标号概念。假设G是一个图,f：V(G)→[0,+∞)是一个映射,s,t是两个非负整数,j,k是实数并且j>k≥1。若对于任一顶点u,至多s个u的邻点标号属于(f(u)-j,f(u)-k]∪ [f(u)+k,f(u)+j),其他邻点的标号属于[0,f(u)-j]∪[f(u)+j,+∞)；至多t个u的2-邻点的标号属于(f(u)-k,f(u)+k),u的其他2-邻点的标号属于[0,f(u)-k]∪[f(u)+k,+∞),则称f是图G的(s,t)-放松的L(j,k)-标号。图的(s,t)-放松的L(j,k)-标号着色的最小跨度定义为图的(s,t)-放松的L(j,k)-标号着色数,记为λj,ks,t(G)。图的(s,t)-放松的L(j,k)-标号这一概念是通过对图的实数L(j,k)-标号作出相应的放松而产生的。若d＝j/k,则λj,ks,t(G)=kλd,1s,t(G)。图的(s,t)-放松的L(j,k)-标号和图的(s,t)-放松的L(d，1)-标号可以相互转化。网格图(六边形网格图、四边形网格图以及叁角形网格图)是频道分配问题中干扰图的理想模型。本文主要考虑各种网格图的(s,t)-放松的L(2,1)-标号着色以及(s,t)-放松的L(d,1)-标号着色问题,研究并得出了它们的一些基本性质,讨论了它们的所有可能的(s,t)-放松的情形。确定了叁种网格图的所有s,t情形下的(s,t)-放松的L(2,1)-标号着色数,确定了六边形网格图的所有s,t和任意d>1情形下的(s,t)-放松的L(d,1)-标号着色数,确定了四边形网格图的几乎所有s,t和任意d>1情形下的(s,t)-放松的L(d,1)-标号着色数(除了s＝0,t＝1,1<d<2这一情形以外),确定了叁角形网格图的大多数情形下的(s,t)-放松的L(d,1)-标号着色数以及其余情形下的(s,t)-放松的L(d,1)-标号着色数的界。这些结果给相应的频道分配问题提供了一系列的频道分配方案。
郭志伟[5]2016年在《图的强平衡顶点荫度若干问题研究》文中研究说明图的平衡着色问题是Meyer[36]于1973年提出并进行研究,目前该主题己经获得了广泛的关注和研究.如果f是从V(G)到{1,2...,t}的一个映射,那么f是图G中的t-着色.令Vi={v|f(v)=i}(1≤i≤t)如果对于所有的i和j有||Vi|-|Vj||≤1,那么图G的t-着色f是平衡的.最近,Wu等人[42]提出了平衡(t,k)-树-着色的概念,这一概念可以看作是真平衡t-着色的一个推广.如果G[Vi](1≤i≤t)的每个分支是最大度不超过k的树,那么这个t-着色f是图G的一个(t,k)-树-着色.一个平衡的(t,k)-树-着色是一个(t,k)-树-着色并且是平衡的.图G的平衡顶点k-荫度,记作vak=(G),是使得图G有平衡的(t,k)-树-着色的最小的整数t.图G的强平衡顶点k-荫度,记作vak≡(G),是使得图G对于每个大于等于t的t'均有平衡的(t',k)-树-着色的最小的整数t.Wu等人[42]研究了完全等部二部图的强平衡顶点k-荫度.他们给出了va1≡(kn,n)不va∞≡(Kn,n)的上界.同时,他们证明当n≡2(mod 3)时,va1≡(Kn,n)达到了上界.随后,Tao等人[40]对当n≡0(mod 3)和n≡1(mod 3)时,va1≡(Kn,n)进行了研究.他们改进了其上界,并且对于一些特殊情形,获得了精确值.在本文中,进一步研究图的强平衡顶点荫度问题.本文的主要研究结果包括以下几个方面：1.研究了完全非等部二部图Kn,n+1的强平衡顶点1-荫度和完全非等部二部图Kn,n+e(1≤e≤n)的强平衡顶点2-荫度.对于va1≡(Kn,n+1)(n≥1),给出其上界.接着,分别对n≡0,1,2(mod 3)的所有情形进行了讨论.当n≡1 (mod 3)时,证明ua1≡(Kn,n+1)达到其上界.当n≡0,2(mod 3)时,令n≡3k+i(i=0,2),又分四种子情形k≡0,1,2,3(mod 4)分别对其进行讨论并改进了它的上界.对于va2≡(Kn,n+e)(1≤e≤n),给出了一个紧的上界.并且证明了当n=3t(t≤2)时,va2≡(Kn,n+1)达到了其上界.2.研究了完全叁部图Kn,n,n的强平衡顶点2-荫度和强平衡顶点3-荫度.对于va2≡(Kn,n,n),当n≡1,2,3(mod 4)时,分别获得了其精确值.当n≡0 (mod 4)时,令n=4k,再分五种子情形：k≡0,1,2,3,4 (mod 5)分别对其进行讨论.对于k≡1,2,3,4(mod 5)的情形,分别获得了其精确值.当k≡0(mod 5)时,给出其上界.对于va3≡(Kn,n,n)(n≥3),首先给出其上界.当n≡0,1,2(mod 4)时,令n≡4k+i(i=0,1,2),又分五种子情形：k≡0,1,2,3,4(mod 5)分别对其进行讨论.当n≡0(mod 4)且k≡1,2,3,4(mod 5)时,分别获得了其精确值.对k≡0(mod 5)时,改进了其上界.当n≡1(mod 4)且k≡2,3,4,0(mod 5)时,分别获得了其精确值.对k≡1(mod 5)时,改进了其上界.当n≡2(mod 4)且k≡3,4,0,1(mod 5)时,分别获得其精确值.对k≡2(mod 5)时,改进了其上界.当n≡3(mod 4),直接获得了va3≡(Kn,n,n)的一个紧的上界.3.研究了一般图的强平衡顶点k-荫度问题.对于一般图,给出了n个顶点的简单图的强平衡顶点k-荫度的界1≤vak≡(G)≤[n/2],并且分别对达到vak≡(G)=1,cak≡(G)=[n/2]及vak≡(G)=[n/2]-1的图进行了等价刻画.同时,也获得了关于一般图的强平衡顶点k-荫度的Nordhaus-Gaddum类型结果.4.研究了关于Cartesian积网络的强平衡顶点k-荫度问题.同时,也讨论了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度.首先,讨论了特殊图类Cn,Pn和Petersen图HP3的强平衡顶点k-荫度.其次,对一般图的Cartesian积网络,获得了其强平衡顶点k-荫度的上下界.接着,对于Cartesian积网络Pn口pm(m≥ n≥2),Gn口Cm(m≥n≥3),Kn□Km(m,n≥3)和超Petersen网络HP4讨论了其强平衡顶点k-荫度.最后,获得了阿贝尔群上度为3的Cayley图的强平衡顶点k-荫度的精确值.
王雅琴, 王彩虹[6]2009年在《几种图类的邻点可区别关联着色》文中研究说明近年来,关于图着色问题的研究得到了许多有价值的结果,同时拓展出若干新的着色.图的邻点可区别关联着色是在图的关联着色概念的基础上提出的一种新的着色概念.本文研究了路、星、扇、轮、完全图的邻点可区别关联着色并确定了它们的邻点可区别关联色数.
孔元[7]2011年在《关于几类图的分数色数与分数全色数的研究》文中进行了进一步梳理图的着色问题是图论中的一个重要研究课题之一.分数着色是顶点着色的一个推广,对于某些具体问题,它能更好地刻画解决,分数色数作为图的重要参数之一,是非常具有研究价值的.在第二章中,首先给出了图的分数色数的几种等价定义,接着研究了几类特殊图的分数色数,包括星图,风车图及在此基础上扩充的相应的冠图及齿轮图.在第叁章中,首先介绍了循环图和图的邻接矩阵的定义,然后通过构造图的最大独立集,研究了两类6-正则循环图的分数色数.在第四章中,介绍了广义Peterson图的概念及它的等价定义,考虑并研究了k=3时的广义Peterson图的分数色数.在第五章中,根据全着色猜想研究了几类Mycielski图的分数全染色,包括星图,扇图,轮图和皇冠图Gn,2,拓展了图染色的领域,便于更好地研究图的结构.
席美丽[8]2008年在《若干图类的邻强边染色与2-强边染色问题研究》文中研究表明具有重要的理论意义和实际意义的各种染色问题,一直是图论中的热点话题之一。离散系统中的许多问题都可以转化为图着色问题,例如,给定图G,不包含子图的G的n个顶点的图的边的最大数目就依赖于图G的色数。因此Jensen和Toft断言:图着色理论在离散数学中处于中心的地位。在现实生活中许多领域都会涉及到将某种对象的集合按照一定的规则进行分类的问题,例如时间表问题、排序问题、排课表问题、存储问题、电路安排、任务分配等等,都与图着色理论密切相关。所谓图着色是指对图中的顶点、边(对平面图而言还有面)等元素按照一定的规则进行分类。对象不同或规则不同,便有各式各样的着色。随着染色理论的发展又出现了许多新的染色,例如:全着色、列表着色、点强全着色、强边着色、强着色、关联着色、圈着色、距离面着色、区间着色、r-强边着色、完备着色及动态着色等,这些染色已成为现在图着色领域中新的热点.对于过去很多未解决的问题我们可以把它转化为一个新的染色问题,使原问题变得简单易懂并且便于研究。本文主要研究的是图的邻强边染色与2-强边染色问题。首先借助于Akbari对树2-强边染色及3-强边染色的研究与张忠辅对树邻强边染色的研究,给出了对树进行2-强边染色时,2-强边色数等于最大度加1的充分条件是具有最大度的两个顶点的距离小于等于2。然后根据圈、完全图、完全二部图、轮图、项链、P_n~2、P_n~3、P_n~4、P_n~5、单圈图、若干联图、方形网格与六角网络的结构特点及其具有最大度的顶点之间的关系,研究了它们的2-强边染色问题,确定了它们的2-强边色数与最大度的关系,并且给出了它们的2-强边染色方案。
王芳[9]2010年在《解图着色问题的一个新的遗传算法》文中指出遗传算法是基于自然进化论和遗传变异理论而产生的一种全局随机搜索算法,其应用优势在于处理传统搜索方法难以解决的复杂和非线性问题。图着色问题是一个经典的组合优化问题,无论在理论上还是工程应用上均有一个良好的应用背景,但它也是典型的NP-完全问题。快速、有效地解决图着色问题有着重要的理论价值和极高的实际应用价值。本文在分析和研究标准遗传算法的基础上,针对图着色问题,提出了一种新的遗传算法。在新的遗传算法中,针对标准遗传算法的缺陷,设计了新的种群初始化方法和遗传算子。新的种群初始化方法用于产生较优的初始种群,在保证种群多样性的同时,提高了算法的收敛速度。在交叉算子中通过改进贪心分割方法保证了大的顶点子集不被破坏。两个新的变异算子既维持了种群的多样性又提高了算法的局部寻优能力。本文将新的遗传算法应用于图着色问题中,并在一些标准算例上进行仿真实验。实验结果表明,改进的遗传算法对于各种类型的图形都能获得良好的寻优能力。
赵敏[10]2006年在《几类图的控制参数的理论与算法》文中进行了进一步梳理近叁十多年来，随着计算机科学和网络通讯技术的飞速发展，图论研究也呈现出异常活跃的趋势，而控制数理论也许是其中发展最快的领域．图的控制数理论作为图论的一个重要研究方向，在相关学科领域，例如计算机科学、通讯网络、编码理论、运筹学以及社会学等领域具有广泛的应用．目前，关于图的控制数理论研究主要集中在四个方面：(1)各类控制参数的界的确定，相互之间关系的研究，以及控制参数与图的其他参数，如色数的关系研究；(2)各类控制参数计算复杂性的研究及其算法的设计；(3)函数控制数及其相关课题的研究；(4)控制数理论在相关学科中的应用研究． 本文所做的工作主要包括以下五部分： 第一，我们确定了一般连通图及无爪立方图上电力控制数的准确上界，并对达到其上界的极值图进行了刻画(有关结果已被《Discrete Mathematics》录用)；并分别讨论了外平面图及一般平面图上电力控制数的界(有关结果已被《Journal of Shanghai University》录用)． 第二，我们研究了两类新的控制函数：负边控制函数和负星控制函数；确定了负边控制数的界，并对达到其上界的阶数为偶数的极值图进行了刻画；并且讨论了这两类控制参数与其他控制参数的关系(有关结果已被《Ars Combinatoria》录用)． 第叁，我们对达到图的2-距离控制数已知上界的极值图进行了完全刻画． 第四，我们给出了二部置换图上无圈控制集的线性时间算法，并研究了叁种情况下直线簇上区间图的最小连通控制集算法(有关结果已发表在《上海大学学报(自然科学版)》)． 第五，我们构造了具有最小可能边数且最小度为κ的任意大的无限唯一κ-可着色图类(有关结果已被《Journal of Shanghai University》录用)．
参考文献：
[1]. 关于若干图类的着色问题[D]. 董桂香. 山东科技大学. 2003
[2]. 图的全染色以及邻点可区别全染色[D]. 陈亮. 重庆大学. 2007
[3]. 若干图着色问题的研究[D]. 许振宇. 山东科技大学. 2003
[4]. 图的放松的距离二标号着色[D]. 戴本球. 东南大学. 2015
[5]. 图的强平衡顶点荫度若干问题研究[D]. 郭志伟. 青海师范大学. 2016
[6]. 几种图类的邻点可区别关联着色[J]. 王雅琴, 王彩虹. 泰山学院学报. 2009
[7]. 关于几类图的分数色数与分数全色数的研究[D]. 孔元. 山东科技大学. 2011
[8]. 若干图类的邻强边染色与2-强边染色问题研究[D]. 席美丽. 大连海事大学. 2008
[9]. 解图着色问题的一个新的遗传算法[D]. 王芳. 西安电子科技大学. 2010
[10]. 几类图的控制参数的理论与算法[D]. 赵敏. 上海大学. 2006