【摘 要】
：
设G=（V,E）是一个简单图.对V（G）的两个子集S和T,若T＼S中的每个顶点都和S中的某个顶点相邻,则称S控制T.特别地,若S控制V（G）,则称S为G的一个控制集；也就是说,对S（?）V（G）,若G中每个不在S中的顶点都和S中的某个顶点相邻,则称S是G的一个控制集.控制数γ（G）定义为G的最小控制集的阶数.图的控制集问题关注对给定图G和输入的数值κ,验证是否有γ（G）≤κ.该问题是算法复杂性理论
论文部分内容阅读
设G=（V,E）是一个简单图.对V（G）的两个子集S和T,若T＼S中的每个顶点都和S中的某个顶点相邻,则称S控制T.特别地,若S控制V（G）,则称S为G的一个控制集；也就是说,对S（?）V（G）,若G中每个不在S中的顶点都和S中的某个顶点相邻,则称S是G的一个控制集.控制数γ（G）定义为G的最小控制集的阶数.图的控制集问题关注对给定图G和输入的数值κ,验证是否有γ（G）≤κ.该问题是算法复杂性理论中经典的NP-完全问题,也是运筹学选址问题的自然模型.基于各种选址问题的实际背景,各种各样的控制集问题被广泛研究,图的控制集理论是目前图论研究发展最快的领域之一.本文主要研究两类控制集问题：配对控制集问题和彩虹控制集问题.设图G=（V,E）是一个没有孤立点的简单图.若V的子集S使得每一个V\s中的顶点都有邻点在s中并且s的导出子图G[s]有完美匹配,则称s是G的一个配对控制集.图G的最小配对控制集的阶数称为图G的配对控制数,记为γpr（G）.Goddard和Henning在2009年提出如下猜想：对任何一个最小度至少为3的n阶连通图G,如果G不是Petersen图,则γpr（G）≤4n/7我们围绕这一猜想开展研究.在第二章中对κ≥4的k-正则图证明了该猜想是正确的.在第三章中对最小度至少为9的图证明了该猜想是正确的.图G=（V,E）的边染色是一个映射c：E→C,其中C为颜色集.设（G,c）是用染色方案c给G的边染色后得到的边染色图.若G的某个子图的所有边都染不同颜色,则称该子图为彩虹子图.若S是由不相交的彩虹星组成的集合且S覆盖V（G）,则称S是（G,c）的彩虹控制星集.（G,c）的最小的彩虹控制星集的阶数称为（G,c）的彩虹控制数,记为γ（G）.在第四章中,我们给出了寻找边染色树（T,c）上的最小彩虹控制星集并得到彩虹控制数γ（T）的一个多项式时间算法.
其他文献
通过对奇异摄动最优控制问题状态解极限性质的深入研究,本文探讨了奇异摄动最优控制问题中空间对照结构的存在性.近年来,对空间对照结构的研究已取得了非常深入的成果,从而为奇异摄动最优控制问题中空间对照结构的研究提供了理论依据.空间对照结构主要分为阶梯状空间对照结构和脉冲状空间对照结构两大类.本文主要讨论阶梯状空间对照结构,它的基本特点是在所讨论区间内存在一点t*（当然也可以存在多点t*）,t*称为转移点
课程名称:"形势与政策"对应章节:"国际形势与政策"篇"推动全球经济治理体系变革,推进‘一带一路’倡议"专题一、点题入题当今世界,正处于"乱花渐欲迷人眼"的变化阶段。各国间的博弈竞争呈现出前所未有的复杂深刻,风险叠加局势动荡,
本文主要研究了亚纯函数值分布和正规族理论,并得到了一些新的结果,这些结果对原来定理做了较大的改进.本文最重要的工作便是得到了一个关于椭圆函数的Picard型定理.1.亚纯函数值分布理论的一个结果.在第二章我们继续研究了Picard型定理,得到了一个关于椭圆函数的Picard型定理,这是本文最重要的工作,具体说我们得到设f是复平面C上的非常数的亚纯函数,h是复平面C上的非常数的椭圆函数.如果f只有重
苔蚁甲族（Tyrini）隶属于鞘翅目（Coleoptera）,隐翅虫科（Staphylinidae）,蚁甲亚科（Pselaphinae）,是长角蚁甲超族（Pselaphitae）下的一个大族。该族成员形态相似,体型中至大型,广泛存在于农、林生态系统中,全部为捕食性昆虫,是食物链和食物网的重要一环,对生态平衡起着重要的作用,是自然界不可或缺的成员。本研究之前,全世界苔蚁甲族已知81属601种,分布于
本文的主要目的是要给出一般型复代数曲面的阿贝尔自同构群的阶的最佳上界。设S是一个一般型光滑极小复曲面,G是S的一个阿贝尔自同构群,即S的自同构群Aut（S）的一个阿贝尔子群。我们证明,如果S的几何亏格比6大,则G的阶|G|的上界为12.5KS2+100,这里KS2为S的第一陈省身数。如果进一步假设G是循环群,则|G|≤12.5KS2+90.并且存在无穷多个曲面的例子可以达到上述上界,且曲面的几何亏
含旋度算子的偏微分方程组在数学物理领域有着广泛的应用.例如经典电动力学中的Maxwell方程组、非线性电动力学中的Born-Infeld模型、描述超导体性质的各种模型等.另一方面,从数学角度看,含旋度算子的偏微分方程组也颇为值得探究.我们观察到含旋度算子的问题有许多不同于含梯度算子的问题的地方.此外,含旋度算子的问题与许多其他的问题有千丝万缕的联系.比如其与Lame算子之间的关联,其正则性问题与通
原子冷却对于原子光学、超冷原子物理以及玻色-爱因斯坦凝聚等领域的研究是至关重要的,而玻色-爱因斯坦凝聚又为凝聚态物质以及量子信息物理的研究提供了实验基础。现在,人们又将注意力转向了如何产生并得到冷的或者超冷的分子样品,因为它们具有与原子不同的许多新的相互作用。化学稳定的冷分子为超高分辨的分子束光谱、超冷化学和碰撞、将来可能实现的分子玻色-爱因斯坦凝聚等研究提供了理想的实验平台。本文将围绕中性分子的
Frenkel—Kontorova（FK）模型出现在1938年,它是由处于周期性外势中的、存在近邻相互作用的粒子构成的一维链。作为非线性物理学中最重要的模型之一,许多非线性现象都可以在该模型中找到,比如混沌、孤子、扭结和呼吸子等等。如今这一模型及其推广形式已经被广泛应用于许多物理系统的研究中,比如像晶体位错动力学、公度-不可公度相变、电荷密度波、Josephson结阵列和干摩擦等等。相比较而言,量
本文研究了特征为素数的代数闭域上的基本典型李超代数和Cartan型李代数的一些结构和表示理论.本文的主要研究成果有下面几个方面：第一部分刻画了基本典型李超代数的普遍包络代数的中心结构.设g=g0（?）g1=Lie（G）是基本典型李超代数,其中G是经典的代数超群,其纯偶群Gev是简约群,满足Lie（Gev）=g0.首先我们证明了中心是交换环,接着本文用两种办法证明了Z（g）无U（g）的零因子,然后说
原子相干操控在量子信息、精密测量和量子成像等领域有着重要的意义。产生原子相干性的常用方法有两种,分别为拉曼散射和电磁诱导透射。拉曼散射在很多科研和工业领域中已经有着广泛的应用,因为拉曼散射产生的散射光场频率与物质能级相关,而且更重要的是散射物质的能级之间还会产生一定的相干性,通过对散射光场和物质相干性进行操控人们将拉曼散射广泛应用于物质检测、精密测量、量子信息、生物成像等众多与我们生活息息相关的技