【摘 要】
:
本文主要研究了图的彩虹不连通染色问题。令G是一个非平凡的边染色连通图。一个边割被称作彩虹边割,如果边割中的任意两条边都染不同的颜色。若图G中的任何两个顶点之间都存在一个彩虹边割分离它们,则我们称图G是彩虹不连通的。若图G的一个边染色使得图G是彩虹不连通的,则称这个染色为图G的彩虹不连通染色。对一个非平凡的连通图G,使得图G是彩虹不连通的所需的最少颜色数被称为图G的彩虹不连通数,记作rd(G)。我们
论文部分内容阅读
本文主要研究了图的彩虹不连通染色问题。令G是一个非平凡的边染色连通图。一个边割被称作彩虹边割,如果边割中的任意两条边都染不同的颜色。若图G中的任何两个顶点之间都存在一个彩虹边割分离它们,则我们称图G是彩虹不连通的。若图G的一个边染色使得图G是彩虹不连通的,则称这个染色为图G的彩虹不连通染色。对一个非平凡的连通图G,使得图G是彩虹不连通的所需的最少颜色数被称为图G的彩虹不连通数,记作rd(G)。我们知道有两种方式来研究图的连通性,一种是使用路,另一种是使用割。彩虹连通染色是从路的角度来研究边染色图的染色连通性的,因此,从割的角度来研究染色图的染色连通性是很自然的。在2018年,Chartrand等人首次通过引入图的彩虹不连通染色的概念从彩虹边割的角度研究了图的染色连通性。事实上,图的彩虹不连通染色有以下的应用背景。在一些非法商品交易中,我们希望可以及时阻止交易并发出信号(某种频率)。一方面我们需要阻断两城市之间所有的路并根据不同的信号来辨别拦截地点;另一方面,我们希望用到尽可能少的频率,以便于降低成本。于是,我们想知道满足上述要求所需要的最少的频率是多少?我们把每个城市视作一个顶点,如果相应的城市有道路连接,则在两个顶点之间添一条边,用G表示得到的图。给图G一个边着色,其中边上的颜色对应该道路发出的频率。于是,上述问题等价于计算图G的彩虹不连通数。本文包括以下六个章节:在第一章,我们首先介绍了图论中的一些基本定义和符号。然后介绍了关于图的彩虹不连通染色的背景及相关概念。最后,我们对彩虹不连通数的相关结果进行了概述。在第二章,我们首先通过构造极图的方式确定了给定彩虹不连通数的连通图的最大边数,这解决了Chartrand等人提出的一个猜想。进而我们得到彩虹不连通数的两类Erd(?)s-Gallai-型问题。此外,我们研究了图的彩虹不连通数的Nordhaus-Gaddum-型问题,并完全刻画了达到上界的图类。在第三章,由图的彩虹不连通数的性质和一些特殊图类的彩虹不连通数的结果,我们得到四色定理和彩虹不连通数的一个等价关系,并且提出一个类似Vizing定理的猜想,即图的彩虹不连通数要么等于图的上边连通度,要么等于图的上边连通度加1。进一步,我们得到对于奇数k,分别存在无穷多个k-边连通k-正则图满足猜想的上下界,并给出一些结论以进一步支持我们的猜想。最后,我们给出rd(G)关于其他参数的上界。在第四章,为了获得一个染色版本的Menger定理,我们引进了图的强彩虹不连通染色的概念,并得到一些关于它的基本性质。同时,我们进一步探讨了图的强彩虹不连通数与彩虹不连通数之间的关系。在第五章,我们分别研究了图的彩虹不连通数和强彩虹不连通数的算法复杂性。我们证明对于一个连通的3-正则图G,确定是否rd(G)=3(或srd(G)=3)是NP-完全的。此外,我们进一步证明对一个给定的边染色图及图中的两个顶点,判定这两点之间是否存在一个彩虹(最小)边割是NP-完全的。在第六章,我们列出了可进一步研究的问题。
其他文献
有机肼类化合物作为原料被广泛应用于含有N–N键单元的杂环化合物如吡唑、哒嗪等的制备,在农药、染料和药物的合成中有重要的应用。其中,β-或γ-位含有官能团的含氮杂环化合物为药物分子的设计和开发带来了更多的可拓展性,也是合成化学中炙手可热的目标结构。本文拟探索几类含有N–N键的不饱和体系作为亲电受体在自由基加成反应中的特性。通过亲核试剂、烯烃与亲电受体之间的极性反转三组分自由基串联反应,建立高效合成含
在中国历史发展的长河中,20世纪80年代具有特殊的时代意义。作为前承“毛时代”革命叙事,后启90年代商品叙事的过渡阶段,80年代不仅是社会发展的重要转折时期,同时也是各类社会文化思潮空前活跃、学术理论启蒙的时期,大量意识形态在此过程中博弈。而正是这种特殊的时代环境,造就了风景园林学科发展由单一模式走向多元互渗的新阶段。基于此背景,本文研究聚焦80年代,在历史文献与实践案例构筑的语境下对该时期风景园
第一部分 实验性自身免疫性心肌炎动态lncRNA-gene表达库的构建目的:通过建立小鼠实验性自身免疫性心肌炎模型,利用lncRNA基因芯片技术构建实验性自身免疫性心肌炎lncRNA-gene表达库。方法:选取6-8周雄性BALB/c小鼠作为研究对象,通过免疫心肌肌球蛋白重链建立EAM模型,所有小鼠被随机分成4组:正常对照组(EAM第0天)、EAM第14天组、EAM第21天组和EAM第62天组。测
2005年,Omar M.Yaghi利用动态可逆共价键策略将分子结构单元扩展成网状排列的结晶的共价有机框架(Covalent Organic Frameworks,COFs)。在有机高分子材料领域,COFs具有许多非常突出的优势,如:长程有序性(高结晶性)、高比表面积、低密度、可功能化、丰富的单体选择等。尤其高有序性的特点,使COFs材料的结构可以清晰地确定,这样结构与性能的关系得以一一对应,进而
由于可以快速制造复杂金属零件,激光选区熔化(Selective Laser Melting,SLM)成形技术的应用前景十分广阔。然而,SLM成形过程中的高温度梯度诱导的零件高残余应力、变形甚至是开裂问题,严重地阻碍了该技术的工程应用。目前对于SLM成形过程中应力的分布和演化及其导致的变形还缺乏系统研究,特别是构成航空航天构件的典型结构的应力及变形研究还几乎是空白。本论文采用有限元数值模拟的方法,系
在过去的几十年中,金属-有机框架(metal-organic frameworks,MOFs)作为晶态材料,由于其独特而多样的多孔结构和功能性受到越来越多的关注。它们在气体存储和分离,非均相催化,传感器,药物输送等众多领域中展现了迷人的应用前景。MOFs组成单元中的金属节点和有机配体具有灵活的可调性和可修饰,因而可以设计和合成具有特殊结构和功能的MOFs材料。但是,目前仍然存在诸多的问题,阻碍了这
我国西北地区龙首山成矿带以世界级的金川铜镍硫化物金属矿床闻名于全球,也是我国西北地区一条重要的铀成矿带。该铀成矿带中发育多种类型铀矿床,包括成矿带西段的红石泉伟晶岩型铀矿床,成矿带中段的新水井、岌岭钠交代型铀矿床以及革命沟花岗岩外带型铀矿床,成矿带东段的金边寺淋积型铀矿床。其中新水井和岌岭铀矿床是我国少有的钠交代型铀矿床,也是我国西北地区碱交代型铀矿床的典型代表。对岌岭钠交代型铀矿床开展系统的研究
近三十年以来,二维材料因其奇异的电子性质,光学性质和磁性质等受到广泛关注。随着理论预测和实验合成,新型二维原子晶体材料不断被发现。这些二维材料不仅揭示了深刻的物理机制,而且在下一代信息技术等方面展现潜在的应用前景。比如,单层MoS2薄膜能够实现“开”和“关”的调控,有望应用于场效应晶体管;钛酸锶表面的单层FeSe薄膜具有高温超导特性;单层CrI3薄膜存在长程铁磁序等。这些新奇现象的发现,对进一步理
铁电材料具有可翻转的电极化性质,能用于非易失性存储器、电容器、传感器和执行器等多个领域。多铁材料将多个基本铁序集中到一个材料中,不仅同时具有铁电性、磁性等性质,还能互相耦合,有望实现新器件的新颖应用。传统的铁电或多铁材料主要是钙钛矿块体材料,比如典型的铁电材料Ba Ti O3,多铁材料Bi Fe O3,这些材料普遍带隙较大、迁移率低;而且它们的薄膜材料存在临界厚度效应,在应用于微型化和集成度越来越
混沌在经典动力学中指具有确定性但不可预测的现象,以受经典运动方程支配的轨道长期性行为为特点。在量子力学领域,由于微分方程关于时间为线性,且由于不确定性原理的影响,轨道没有得到良好的定义,不存在严格的混沌现象。量子混沌研究的是经典系统中的动力学行为在所对应量子系统中会有怎样的特征。其中著名的结论有Bohigas-Gianonni-Schmit猜想和Berry-Tabor猜想。它们表明对应于经典动力学