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

来源 :南开大学 | 被引量 : 0次 | 上传用户:kekexiaozi
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
控制理论是图论中的一个重要分支,它在计算机科学、通讯网络、社会关系学等领域都有着广泛的应用。随着计算机科学和网络技术的不断兴起,控制理论的研究得到了迅猛的发展。求图的控制数的问题是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-因子临界的。   第四章,我们介绍了一些在其他控制参数下的临界图及其这方面的研究结果。
其他文献
在现实复杂的经济环境中,古典风险模型并不能很好的描述保险公司的运转,所以一直以来大家都致力于古典风险模型的推广,以使其更能刻画现实中保险公司的业务运行。通常保险公司将
本文研究非精确方法的收敛性和逆特征值问题的求解,给出了非精确方法的局部收敛性和半局部收敛性并且提出了若干种求解逆特征值问题的方法和它们的收敛性分析.本文主要内容分两
本文讨论无约束优化近似求解问题,在二次模型近似求解的基础上,讨论一种三次模型信赖域问题。信赖域算法是求解无约束最优化常用的方法之一,通过用泰勒展开式近似目标函数,把目标
1748年Euler建立了整数分拆的一个生成函数,基本超几何级数的研究由此开始。此后,Gauss、Heine、Rogers、Ramanujan、Watson和Slater等数学家做出了很多重要的成果,极大地推动了
本文讨论的是带有随机时滞的一类网络控制系统的H_∞输出跟踪控制问题。在连续时间网络控制系统的H_∞输出跟踪控制问题中,不仅考虑了传感器到控制器之间的网络产生的随机时
第一章主要考虑带粗糙核的奇异Radon变换在Lebesgue空间上的有界性.Radon变换的研究受Christ等人的启发,第一章的第二节证明了下面的结论定理1.1设r(x,t)在x0点满足曲率条件(C)
本文介绍了基于流形的机器学习算法--流形学习。其中包括等距映射、局部线性嵌入映射、拉普拉斯特征映射和扩散映射,展现了这些经典算法的思想、推导过程以及实验效果,并在此基
本文首先利用B网方法和最小决定集技术,构造了一类四边形三角化剖分下二元二次样条空间S21((?))的一个最小决定集,并给出了它的维数.接着针对非均匀Ⅱ型三角剖分下二元三次样条空
算子代数理论产生于20世纪30年代.随着这一理论的迅速发展,现在这一理论已成为现代数学中的一个热门分支.它与量子力学、非交换几何、线性系统、控制理论、数论以及其他一些重要
设г是有限无向简单正则图.若г没有孤立点,我们称图г是弧传递的或对称的,如果г的自同构群Aut(г)传递地作用在г的弧集合上.本文讨论了完全三部图K2,2,2的弧传递Zn-正则覆盖,得到