【摘 要】
：
随着很多实际问题可以转化为图论问题,图染色发挥越来越重要的作用。作为图连通染色的割版本问题,Chartrand等人在2018年提出了图的彩虹不连通染色。基于图的彩虹顶点连通染色和彩虹不连通染色,同时,为解决频率分配,货物拦截中的相关问题,Bai等人提出了图的彩虹顶点不连通染色。本文主要研究了图的彩虹顶点不连通染色。令G是一个非平凡连通的顶点染色图。对于图G的顶点子集X,如果X中的任意两个顶点有不同
论文部分内容阅读
随着很多实际问题可以转化为图论问题,图染色发挥越来越重要的作用。作为图连通染色的割版本问题,Chartrand等人在2018年提出了图的彩虹不连通染色。基于图的彩虹顶点连通染色和彩虹不连通染色,同时,为解决频率分配,货物拦截中的相关问题,Bai等人提出了图的彩虹顶点不连通染色。本文主要研究了图的彩虹顶点不连通染色。令G是一个非平凡连通的顶点染色图。对于图G的顶点子集X,如果X中的任意两个顶点有不同颜色,那么我们称X是彩虹的。如果对于图G的任意两个顶点x和y,存在顶点集S,使得当x和y 不相邻时,S是彩虹的,且x,y属于G-S的不同分支;而当x和y 相邻时,S+x或S+y是彩虹的,且x,y属于（G-xy）-S的不同分支。那么我们称图G是彩虹顶点不连通的。此时,称顶点集S是图G的一个x-y彩虹顶点割。对于连通图G,它的彩虹顶点不连通数是指使图G彩虹顶点不连通所需的最小颜色数,用rvd（G）表示。本文共分七个章节,具体如下:在第一章中,我们给出了本文的相关概念和符号,讲述了彩虹顶点不连通染色的应用背景,并介绍了相关研究现状。同时,我们也介绍了本文的主要结果。在第二章中,我们首先给出了一些关于图的彩虹顶点不连通数的基本结果。然后,对于n个顶点的图,我们分别刻画了彩虹顶点不连通数为1,2,n-1和n的所有图。我们也根据不同的参数,给出了彩虹顶点不连通数的界。我们证明了 δ（G）≤κ+（G）≤rvd（G）≤Δ（G）（Δ（G）-1）+1,其中 δ（G）为图 G 的最小度,Δ（G）为图G的最大度。如果图G的独立数为α（G）,那么我们有rvd（G）≥[n/2α（G）]。对于n个顶点的围长为g>4的非平凡连通图G,我们证明了rvd（G）≤n-g+2;对于n个顶点的直径为d的非平凡连通图G,我们证明了rvd（G）≤n-d+2。此外,根据其他参数,我们也给出了一些结果。在第三章中,我们讨论了特殊图和随机图的彩虹顶点不连通数。我们首先给出了轮图和完全多部图的彩虹顶点不连通数。其次,我们给出了笛卡尔积图、四角系统、苯环系统的结果。我们也考虑了外平面图,证明了它的彩虹顶点不连通数不超过4。此外,在随机图上,我们得到了关于性质rvd（G（n,p））=n的一个紧的门槛函数。我们也证明了几乎所有图G满足rvd（G）=rvd（G）=n。在第四章中,我们研究了关于彩虹顶点不连通数的极值问题。我们先研究了非平凡连通图的彩虹顶点不连通数为k时边数的最小、最大值,并给出了相对应的Erdos-Gallai-型结果。然后,我们研究了图和补图之间的彩虹顶点不连通数关系,给出了 Nordhaus-Gaddum-型结果。我们证明了对于顶点数n≥24的非平凡连通图 G 和G,有n-5≤rvd（G）+rvd（G）≤ 2n 和n-1≤rvd（G）·rvd（G）≤n2。在第五章中,我们研究了图的彩虹顶点不连通的算法复杂性。我们证明了对于给定顶点染色的图G,确定它是否是彩虹顶点不连通的是NP-完全的,即使图G满足Δ（G）=3或者是二部的。在第六章中,我们提出了一些可以进一步研究的问题。
其他文献
蛋白质结构决定其功能,了解蛋白质的结构对蛋白质的靶向药物设计和功能注释有重大意义。然而,通过湿实验技术确定蛋白质结构成本高且耗时,而当前蛋白质结构预测算法的精度仍有待提高。核酸往往通过与其它分子（如蛋白质、金属离子等）的相互作用执行其生物学功能,准确识别核酸与其它分子的结合位点可以加速计算机辅助药物的设计。然而,现有的核酸与其它分子的结合位点预测算法的准确率相对较低。因此,本文针对这两个方面展开了
零和理论是组合数论中一个重要的分支,近年来零和理论发展迅速并且得到了广泛的关注。零和理论的一个基本研究课题是研究具有特定性质的零和子列的存在性条件,由此提出了许多关于有限阿贝尔群的不变量,例如,EGZ-常数、Davenport常数、η-常数等。上个世纪70年代,R.Graham提出研究具有不同长度的零和子列问题。他猜想p阶循环群上的一个p长序列如果有3项两两不同,那么该序列一定包含两个具有不同长度
近年来,由于RNA的三维结构数据增长较为缓慢,人们对RNA的生物功能机制无法得到进一步了解,并且也影响了靶向RNA的小分子药物的研发。因此,急需开发优秀的计算方法来预测RNA三维结构。但是目前,RNA的三维结构预测仍是一个巨大的挑战。因此,鉴于蛋白质三维结构预测领域的研究,本文首先利用已有的三维结构数据专注于RNA的三维结构特征与功能预测。本文主要开发了两个RNA结构特征预测算法和一个RNA功能预
1994年,编码学者发现一些重要的非线性二元码可以由Z4上一些特殊的具有好的结构的线性码通过Gray映射构造.在此之后,编码学者开始研究有限环上的纠错码理论.本文在已有研究成果基础上,发展有限环和有限域上的纠错码理论,研究有限环上线性码的覆盖半径,有限环上斜常循环码和斜循环码的代数结构以及有限域上优化码的构造,获得有限域上具有较好参数的线性码并将其应用于构造新的量子纠错码.具体内容如下:第一章,介
本学位论文在有理同伦论中,对映射空间,分类空间和本征形式空间进行了研究.本学位论文主要结果如下.（一）本文证明映射空间map（X,Y）的有理同伦型只依赖于X的上同调代数和Y的有理同伦型,其中X是有限的CW-复形,Y是有限型的有理的CW-复形且其极小Sullivan模型形如（Λ（P⊕Q）,d P=0,d Q（?）ΛP）.证明的主要方法是对map（X,Y）的L∞-代数模型应用同伦变换定理.利用上述结果
作为一种研究各类复杂过程和系统的工具,试验设计广泛应用于科学研究、工业、农业、医学等多个领域。试验设计可以分为单次设计和序贯设计。单次设计是一次性完成固定次数的试验,而序贯设计逐次地序贯添加设计点直到达到试验目标。作为一种经济有效的方法,序贯设计既可以避免盲目加大试验样本个数而造成浪费,又不至于因试验样本个数太少而无法得到结论。随着计算机技术的飞速发展,现有的序贯设计已经无法满足各类具有复杂结构试
在[]中,R.Kato和K.Shimomura使用第三个Morava稳定子代数的上同调检测球面稳定同伦群中希腊字母元素的非平凡乘积.本文我们使用他们的方法发现了球面稳定同伦环中希腊字母元素新的乘积:令p ≥ 7,有0≠ξnγsβ1∈π*S,如果n三2 mod 3,s（?）0,±1 mod p.并且写出球面稳定同伦环中α-族,β-族,γ-族,以及R.Cohen元素ξn的乘积中所有能被上同调H*S（3
同时定位与建图（Simultaneous Localization and Mapping,SLAM）是通过对传感器信息的处理,在未知环境中对移动机器人进行定位,并建立环境地图的过程。近年来,随着移动机器人在家庭服务、自动驾驶等领域的应用,SLAM技术也随之得到广泛的研究和发展。基于环境特征的机器人位姿求解与环境建模,是SLAM技术的主要实现途径。面向复杂多样的作业场景,不同种类的特征有着各自的优
本论文主要研究点拟本原边传递图的自同构群和边本原图的分类问题。图的对称性（比如边传递性、弧传递性等）和自同构群是代数图论中的重要研究对象,在其研究过程中群的理论和方法发挥了不可替代的作用。特别是针对具有一定传递性质的图类,许多问题被归约到了拟本原甚至是几乎单的情形。这是本文所进行研究的主要动机。本文的第一项主要工作是关于点拟本原边传递图的研究。设Γ是连通的2倍素数度的G-边传递图,其中G是Γ自同构
本文研究了几类结构张量的理论性质及其张量互补问题,主要讨论了非负Q-张量的张量互补问题解集的具体上下界;Cauchy-Hankel张量特征值的上界;矩形Z-张量、矩形P-张量的性质及相应互补问题解的存在情况。并运用相关算法来计算张量的特征值。论文结构如下:首先,对由张量互补问题可解性定义的Q-张量给出一些新的结果。对于这类结构张量,我们给出了充分条件来保证其相应的张量互补性问题的非零解至少包含两个