论文部分内容阅读
图的控制数的计算是NP-完备问题,因此探索图的控制数的精确值或较好的上下界具有较大的理论意义.强罗马控制数是一类重要的控制数,不仅在蛋白质结构的研究、电路图设计、计算机编程等方面有着广泛的应用,而且在逻辑学、语言学、通讯网络、人工智能等科学领域的应用也尤为突出.本文主要应用数学归纳法和分类讨论法,深入讨论了图的强罗马控制数与阶数的关系,得到了风车图、完全二部图、完全图的刺图等特殊图上的强罗马控制数均不大于其阶数的七分之六.