对一些控制参数下的临界图的研究

《对一些控制参数下的临界图的研究》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、摘要控制理论是图论中的一个重要分支，它在计算机科学、通讯网络、社会关系学等领域都有着广泛的应用。随着计算机科学和网络技术的不断兴起，控制理论的研究得到了迅猛的发展。求图的控制数的问题是NP-C的，所以一般图的控制的研究是比较困难的。对于图的控制数，如果从一个图中删去一个点，则控制数可能增大、减小或者不变。假如给定一个图，任意删去其中一个点后得到的图的控制数比原来小，我们则称这个图是控制点临界图。对于加边的操作来说，众所周之加上一条边是不会增加图的控制数的。如果任意加上一条边，这个图的控制数变小，我们则称这个图为控制边临界图。1983年，Sumner最先开始对控

2、制边临界图进行研究；1984年，Brigham等人对控制点临界图进行研究。在控制数为1或2时，控制点临界图和控制边临界图已经得到完全的刻画。但是当控制数大于等于3的情况，这些图的刻画还远没有解决。在本文中，我们着重研究控制数为3的情况下的控制点临界图和控制边临界图。第一章，我们介绍图论中的一些基本概念、术语、符号及一些控制理论的基本知识。．第二章，我们主要对控制点临界图进行研究，研究集中在禁止子图情况下的因子方面的性质，主要得到了下面这些结果：1．设图G是3．控制点临界图，如果它有偶数个顶点且最小度至少为3，那么G是3．连通的。2．设图G是3．控制点临界图，如

3、果它不包含导出的蜀．4子图，且有偶数个顶点、最小度至少为4，那么G是双因子临界的。3．设图G是3．控制点临界图，如果G不包含导出的墨．5子图、2．连通的、有奇数个顶点且最小度至少为3，那么G是因子临界的或是两个特定的图。4．设图G是3．控制点临界图，(D如果G不包含导出的蜀．6子图，G有偶数个顶点且不等于12，那么G有完美匹配。(Ⅱ)如果G不包含导出的蜀．7’有奇数个顶点且只有一个奇分支，顶点数不等于13，那么G有近似完美匹配或者是两个特定的图。第三章，我们主要对控制边临界图进行研究。第一节，主要介绍一些已知的结果，包括3一控制边临界图的哈密顿性的证明。第二节

4、，主要给出Ananchuen和Hummer的一个猜想的证明，证明了如下结果：假设G是一个3．控制边临界图，七是一个正整数，七和图的顶点数同奇偶，如果这个图是k．连通的无爪图且最小度至少为k+1，那么G是缸因子临界的。第四章，我们介绍了一些在其他控制参数下的临界图及其这方面的研究结果。关键词：控制、控制点临界图、控制边临界图、哈密顿圈、完美匹配、近似完美匹配、因子临界、直径临界图AbstractDominationtheoryisanimportantbranchofthegraphtheory,itcanbeusedinthecomputerscience，n

5、etworks，societystudyandSOon．Withthedevelopmentofcom-purerscienceandnetworks，thedominationtheoryhasmadeimportantgrowth．ThedominationproblemisNP-C，SOthestudyofdominationisveryhard．Forthedomi—nationnumber,itmaydecrease，increaseorequaltotheodgiIlalvaluebyremovingavertexfromagraph．Ifther

6、emovalofanyvertexfromthegraphdecTeasethedomina-tionnumber,thenthegraphiscalleddominationvertexcritical．Butfortheadditionofanedgetoagraph，thedominationnumberCanonlybedecreased,Orequaltotheone．Iftheadditionofanyedgedec他粼thedominationnumber,wecallthegraphdominationedgecritical．Inthisdi

7、ssertation。weconcentrateonthedominationVertexcriticalanddominationedgecriticalgraphsfordominationnumber3．In1983，Sumnerinitiatedthestudyofdominationedgecriticalgraphsresearch；in1984．Brighameta1．beganthestudyofdominationvertexcriticalgraphs．ForthesetWOclassesofgraphs，thecharacterizati

8、onofthemfor7S2iseas