论文部分内容阅读
近年来，图的控制理论及其相关问题是图论中一个比较活跃的研究领域，它是从实际的应用领域提出来的.研究它不仅具有重要的理论意义，而且在通讯网络的设计与分析、优化理论、社会科学、计算的复杂性和算法设计等很多领域也有广泛的应用.由于确定一个图的控制数是NP-完全的，因此目前只有少数图的控制数已经得到很好研究。 本文主要研究了，I-图和广义Petersen图的控制数.在已有研究成果Pe-tersen图存在有效控制集的充分必要条件的基础上，得到了，I-图I(n，j，mj)存在有效控制集的充分必要条件，进而得到了当m=1，2，3时I(n，j，mj)的控制数，并随之得到了I-图，(n，j，mj)的一些性质.此外，在已有研究成果广义Petersen图P(ck，k)的控制数的上界的基础上，得到了P(n，4)的控制数的一个较好的上界.全文共分4章。 第一章，综述了图的控制数的研究背景以及研究进展，并介绍了一些图论的基本概念和控制理论的预备知识，同时还介绍了本文的主要工作。 第二章，主要研究了，I-图，(n，j，mj)的控制数问题.首先，证明了j=k时，I-图即I(n，j，j)的性质，进而推出I(n，j，mj)的性质；然后，利用I-图的性质证明了I(n，j，mj)存在有效控制集的充分必要条件，并且得到了m=1，2，3时I(n，j，mj)的控制数。 第三章，主要研究了广义Petersen图P(n，4)的控制数.利用P(c·4，4)(c≥4)的控制数的上界的研究方法推导出P(n，4)n≥16)的控制数的一个较好的上界，继而得到P(n，4)n≥9)的控制数的上界。 第四章，对本文进行总结，概述本文的主要结论以及对未来工作的展望。