论文部分内容阅读
近几年来,图的控制理论以及与其相关的一些课题如图的染色、完全控制理论,在图论中一直是比较活跃的研究领域。研究图的控制理论不仅有重要的理论意义,对后面的图论的研究提供必要的理论基础,在通讯网络的设计与分析、交通路线的优化理论、社会科学、算法的计算的复杂性和设计等很多领域也都有广泛的应用。然而,由于确定一个图的控制数是NP-完全的,因此目前只有少数图的控制数已经得到精确值。 本文主要研究了广义Petersen图的控制数以及给定控制数的相关树的离心距离和,全文共分4章。 第一章,综述了图的控制数的研究背景以及研究进展,并介绍了一些图论的基本概念、控制理论以及离心距离和的预备知识,为后面的研究打好理论基础,同时介绍本文的主要工作。 第二章,研究广义Petersen图P(n,5)的控制数。这一章为本文的主要部分,利用P(c·5,5)(c≥4)以及P(n,4)的控制数的上界的研究方法,将P(n,5)(n≥20)的控制数按照n=5c,5c+1,5c+2,5c+3,5c+4(c≡0,1,2,3(mod4))进行划分,推导出P(n,5)(n≥20)的控制数的一个较好的上界,继而得到P(n,5)(n≥11)的控制数的上界。 第三章,研究控制数为5的树的最大离心距离和的树的结构。利用控制数为4的树的最大离心距离和的研究方法推导出控制数为5的树的最大离心距离和,通过反证的方法对不同结构的图进行分析和论证,从而得出结论:在树的所有n(n≥15)阶树中,P13([n-13/2],[n-13/2])的离心距离和最大。 第四章,总结与展望,概述本文的主要结论,并且希望今后能将控制数的相关知识进行扩大和推广,从而更多地应用到实际领域中。