论文部分内容阅读
图论是研究事物以及事物之间关系的一门学科。在日常生活中的一些问题可以转变成图论方面的问题。图的控制数问题是NP-完全问题,给出图的控制数或较好的控制数的界是比较困难的研究课题,所以仍然存在大量结构复杂的图的控制数有待研究。 本文研究了路径交图Pm□Pn的全符号控制数。路径交图是一类大规模图,研究其全符号控制数要考虑点和边的全邻域,具有一定的复杂性。本文根据路径交图的性质和特点,进行数学推导,证明了路径交图的下界;利用分支限界条件,计算机编程找到了路径交图Pm□Pn的上界。通过一系列定理证明,最终得到了m,n≥2时图Pm□Pn的全符号控制数较好的上下界。 本文还研究了Petersen图P(n,3)的意大利控制数。Petersen图是图论中的经典图,是3-正则图。意大利控制数是最近几年兴起的一个控制数概念。本文设计有效的分支限界条件,利用计算图的控制数算法和计算机辅助找到一个上界,根据Petersen图P(n,3)的特点,将函数值进行分解,分情况逐一讨论证明了一个紧的下界,最终确定了Petersen图P(n,3)的意大利控制数确定值。