论文部分内容阅读
Euler的第一篇关于图论的论文发表以后,图论各方面的理论研究渐渐萌芽并一步步趋于完备。在图论领域中,图的控制理论拥有不可替代的理论价值并享有较高地位:首先,各种现实问题的提出,促进了图论知识在建模中的运用,图的控制数问题的研究加快了问题解决的速度;其次,图的控制理论对比于图的其他方面的研究地位也更加与众不同,再次,它对于其他学科的发展的影响也更大,如运筹学,优化理论,组合网络优化,组合理论,博弈论,化学,物理学,电子学,建筑学等。在图的各种理论范围内,得到并给出图的控制数是一个最基本的问题,Garey和Johnson早已在文献[1]中先后给出了证明:完备问题控制数是一个确定任意一个给定图的 NP-。综上可知,得到并确定图的控制数并使其结果尽可能好,拥有不可或缺的现实意义。 本文主要工作如下: 本文主要从号控制四方面陈述。制,符号圈控制,圈符符号边控制,符号星控 在本文第一章的绪论中,对图论和图的控制理论的产生背景、未来前景、应用领域以及主要的所得的研究成果和研究趋势做了简要总结,随后对相关方面的定义、符号、意义、图与图的运算关系等做了简要说明,最后对自己将要研究的主要内容及架构做了简单陈述。 在本文第二章,介绍了图的符号边控制定义及部分理论,尤其是一些特殊图的符号边控制的结论,借用其研究方法,为下文的符号星控制奠定基础。 在本文第三章,在特殊图Pm×Pn和Pm×Cn的符号星控制数的研究基础上,新定义了广义轮图和广义扇形图。对其特性详细研究后,确定了这两类图的符号星控制数。此外还给出了如Peterson图、3方体、2方体、塔形图、G(k,4)、G(k,3)等简单图的符号星控制数。 广义轮图W(m,n)的符号星控制数为(此处省略公式) 广义扇形图F(m,n)的符号星控制数为(此处省略公式) 本文第四章,首先证明了一般图的圈符号控制数的界限、达到相应界限的条件、相关论断,其次总结了图的符号圈控制中的部分理论,最后提出了有待探讨的问题。 本文第五章,对前面得到的已有的结果和新的结论做了简单的总结和回顾,此外本文还对图的控制理论进行了展望,希望所得结论对以后的研究有一定的指导意义。