局部竞赛图中点不交的圈和二次邻域

来源 :山西大学 | 被引量 : 0次 | 上传用户:muscleprince
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
竞赛图作为有向图中特殊的一类图,自然成为研究与有向图相关问题的重要对象之一.随着局部半完全有向图的概念和全面分类的提出(特别地,无2-圈的局部半完全有向图是局部竞赛图),作为竞赛图的推广图,局部竞赛图成为继竞赛图之后的重点研究对象之一.在竞赛图中已经解决的问题,研究者往往会在局部竞赛图中继续探究.圈和二次邻域问题一直是图论学者们研究的重点,本文将在局部竞赛图中继续研究竞赛图中已经被解决的一些关于圈和二次邻域的如下问题:1981年,Bermond和Thomassen提出猜想:对任意正整数r,最小出度不小于2r-1的有向图中至少存在r个点不交的圈.1990年,Seymour提出猜想:定向图中总存在一点,满足它的二次外邻的个数不少于外邻的个数.2006年,Sullivan提出猜想:(1)定向图中总存在一点,满足它的二次外邻的个数不少于内邻的个数;(2)定向图中总存在一点,满足它的二次外邻与外邻的总个数不少于内邻的个数的2倍.特别地,在竞赛图中,2010年,Lichiardopol提出猜想:对任意正整数q≥3和r≥1,最小出度不小于(q-1)r-1的竞赛图中至少存在r个点不交的q-圈.因为Bermond-Thomassen猜想和Lichiardopol猜想都是与圈有关的猜想,所以本文主要在局部竞赛图中研究点不交的圈,Seymour猜想,Sullivan猜想,共分为四章.第一章是绪论.介绍有向图的基本概念,局部竞赛图的定义和结构,以及本文内容的安排.第二章,在局部竞赛图中研究Bermond-Thomassen猜想,通过证明得到:(a)Bermond-Thomassen猜想对局部竞赛图是成立的,即任意正整数r,最小出度不小于2r-1的局部竞赛图中至少存在r个点不交的圈.在竞赛图中研究Lichiardopol猜想,通过证明得到:(6)当r ≤ 3时,Lichiardopol猜想是成立的,即对任意正整数r,q ≥ 3,最小出度不小于(q-1)r-1的竞赛图中至少存在r个点不交的q-圈.第三章,在局部竞赛图中研究Seymour猜想.为了表示方便,称满足Seymour猜想的点为Seymour点.通过证明得到:(a)圆可分解的局部竞赛图中总存在一个Seymour点.(b)无出度为0的圆可分解的局部竞赛图中至少存在2个Seymour点.(c)最小出度δ+(D)=a的非圆可分解的局部竞赛图D(并且不是竞赛图)中存在一点v∈V(D),使得d++(v)≥γd+(v),其中 γ=min{3/4+1/2a,(?)}.第四章,在局部竞赛图中研究Sullivan猜想.为了表示示方便,称满足Sullivan(i)猜想的点为Sullivan-i点,其中i ∈ {1,2}.通过证明得到:(a)局部竞赛图中总存在一个Sullivan-i点,这里i ∈ {1,2}.(b)无入度为0的局部竞赛图中至少存在2个Sullivan-1点.(c)无入度为0的圆可分解的局部竞赛图中至少存在2个Sullivan-2点.(d)无入度为0的非圆可分解的局部竞赛图D(并且不是竞赛图)中至少存在2个Sullivan-2 点或存在一个满足 d++(x)+d+(x)≥ 2d-(x)+2 的 Sullivan-2 点.
其他文献
随着信息技术和互联网的快速发展,各行各业尤其是计算机行业产生和积累了大量的数据,而且海量数据仍然源源不断的继续产生和积累。因为数据的规模和它们的复杂性,海量数据在单个机器上很难被处理,传统的数据存储和管理工具及处理算法和数据处理已经变得不能使用或者效率变得极其低下,难以接受的程度。人们迫切需要从海量数据中查询、提取和分析出他们需要的信息,以便快速做出进一步的决策或制定下一个工作方案。图被广泛用于描
随着中国经济进入新常态,城市逐渐摆脱各自为政的发展模式,转变为联系紧密的城市群发展模式,要素禀赋各异的城市在城市群中发挥不同的功能,通过城市群内功能分工促进城市经济增长。与此同时,中国流域众多,流域经济一直以来在中国经济发展中占有重要地位,研究流域城市群的功能分工,有助于流域城市的协调发展,进而促进流域经济增长。本文综合运用理论分析和实证分析方法,深入分析城市群内功能分工对流域经济增长的影响。以长
胡宏作为湖湘学派的代表人物与奠基者,其思想一度没落。牟宗三通过《心体与性体》一书高度推举其哲学思想,认为是超出程朱和陆王的第三系,并且认为它是唯一的圆教体系,从而引发了学界对此的研究热潮。不同于理本论和心本论,胡宏主张“性”是宇宙万物的本原和存在依据。因为万物皆是气化而形成,而性决定了气的运动变化,所以胡宏所言之“性”不仅指人之性,还和朱熹所说之“理”是一致的。那么人如果想最终实现至善之性,则需要
由于声空化可以产生显著的机械和化学效应,在生物医学、化学工程等有很多重要的应用。在多个外加声场驱动下,空化效应可以得到增强,例如,声致发光的强度提升、声化学反应器的
松科1井青一段到嫩二段发育大套丰富的泥岩,其岩相类型变化差异大,有机地球化学特征非均质性强。前人对岩性进行了精细描述,并且分析了有机地球化学特征,但是未对细粒岩相进
准中4区块头屯河组油气藏类型主要以岩性圈闭油气藏为主,因此砂体的分布成为了重要的控藏因素。通过本文的研究,最终确定了曲流河河道,三角洲分流河道和滨浅湖滩坝是工区头屯
经历了漫长且复杂的地质年代,自然界中的岩体在复杂的物理化学等变化下形成了具有一定形态、成分各异的地质体,在这些地质体中发育形成了许多不连续面。在地壳上部,最常见的
为探讨沙旱生植物的形态及组织结构对地域分异的响应,研究植物形态、结构的地域分异规律,本研究以呼伦贝尔沙地、科尔沁沙地、浑善达克沙地及毛乌素沙地的羊柴(Hedysarum laeve)、小叶锦鸡儿(Caragana microphylla)、小果白刺(Nitraria sibirica)为研究对象,采用野外测量、石蜡切片技术及叶片解离技术,观察、分析三种植物茎、叶形态及组织结构的地域分异特征,并就其
腿式移动机器人是通过足端支撑点的交替变化实现移动功能的。这样的移动方式使得腿式移动机器人能够很好地适应崎岖地形,并能够攀越一定高度的障碍物。其中四足移动机器人有比双足移动机器人更强的承载能力、更好的平稳性,有比六足等多足移动机器人更大的腿部移动空间、更小的机构冗余性和复杂度。因此,四足移动机器人一直是国际上移动机器人领域的研究热点之一。本文设计了一种基于并联机构的四足移动机器人。四个结构相同的机械
党的十八届五中全会提出把“共享”作为五大发展理念之一,是对经济社会发展理念的创新,也是新形势下推动社会经济发展的基本遵循和重要指南。发展理念是发展实践的理论导向,有什么样的发展理念就有什么样的发展道路、发展范式。共享发展理念与高校思想政治教育结合,既是共享发展理念落实、落细的重要举措,又是实现高校思想政治教育创新的必然要求。因此,我们要正确挖掘并善用共享发展理念,使之与高校思想政治教育紧密结合,开