论文部分内容阅读
控制理论是图论中的一个重要分支,它在计算机科学、通讯网络、社会关系学等领域都有着广泛的应用。随着计算机科学和网络技术的不断兴起,控制理论的研究得到了迅猛的发展。求图的控制数的问题是NP-C的,所以一般图的控制的研究是比较困难的。对于图的控制数,如果从一个图中删去一个点,则控制数可能增大、减小或者不变。假如给定一个图,任意删去其中一个点后得到的图的控制数比原来小,我们则称这个图是控制点临界图。对于加边的操作来说,众所周之加上一条边是不会增加图的控制数的。如果任意加上一条边,这个图的控制数变小,我们则称这个图为控制边临界图。
1983年,Sumner最先开始对控制边临界图进行研究;1984年,Brigham等人对控制点临界图进行研究。在控制数为1或2时,控制点临界图和控制边临界图已经得到完全的刻画。但是当控制数大于等于3的情况,这些图的刻画还远没有解决。
在本文中,我们着重研究控制数为3的情况下的控制点临界图和控制边临界图。
第一章,我们介绍图论中的一些基本概念、术语、符号及一些控制理论的基本知识。
第二章,我们主要对控制点临界图进行研究,研究集中在禁止子图情况下的因子方面的性质,主要得到了下面这些结果:
1.设图G是3-控制点临界图,如果它有偶数个顶点且最小度至少为3,那么G是3-连通的。
2.设图G是3-控制点临界图,如果它不包含导出的k1,4子图,且有偶数个顶点、最小度至少为4,那么G是双因子临界的。
3.设图G是3-控制点临界图,如果G不包含导出的K1,5子图、2-连通的、有奇数个顶点且最小度至少为3,那么G是因子临界的或是两个特定的图。
4.设图G是3-控制点临界图,(I)如果G不包含导出的K1,6子图,G有偶数个顶点且不等于12,那么G有完美匹配。(II)如果G不包含导出的K1,7,有奇数个顶点且只有一个奇分支,顶点数不等于13,那么G有近似完美匹配或者是两个特定的图。
第三章,我们主要对控制边临界图进行研究。第一节,主要介绍一些已知的结果,包括3-控制边临界图的哈密顿性的证明。第二节,主要给出Ananchuen和Plummer的一个猜想的证明,证明了如下结果:
假设G是一个3-控制边临界图,k是一个正整数,k和图的顶点数同奇偶,如果这个图是k-连通的无爪图且最小度至少为k+1,那么G是k-因子临界的。
第四章,我们介绍了一些在其他控制参数下的临界图及其这方面的研究结果。