论文部分内容阅读
图的控制理论是图论中的一个重要研究领域,这篇论文主要研究了“给定控制数的二部图的最大边数”和“3正则图的电网控制数”这两个问题。
第一章,介绍了图论的应用和一些相关概念。
第二章,研究了图的控制数、独立控制数、全控制数、连通控制数和它们的上下界。
第三章,研究了给定控制数的二部图的最大边数问题。我们证明了若二部图G的最大度不等于(「)n-γ(G)+2/2」或(「)n-γ(G)+2/2(」),则它的最大边数为(「)(n-γ(G))2+4(n-γ(G))/4」,我们还给出了连通的极值图,这一结果改进了陈宏宇和张丽的结果[给定控制数的连通二部图的最大边数,山东大学学报,2012]并解决了他们提出的问题。
第四章研究了3正则图的电网控制数问题。Haynes等人[SIAM DM,2002]建立了监测电力系统的图的电网控制模型,集合S称为图G的电网控制集如果通过电力系统的一系列观测规则可以观测到图G的所有顶点和边。图G的电网控制数,记为γ(P)(G),是最小电网控制集的顶点个数。Haynes等人[SIAMDM,2002]证明了对任意n阶树T有γ(P)(T)≤n/3,赵敏等人[DM,2006]证明了这个上界同样适用于n阶连通图,他们同时证明了对于claw-free的n阶3正则图有γ(P)(G)≤n/4,这使得我们开始研究一般3正则图的电网控制数,我们证明了对于3正则的Hamilton图、亚Hamilton图均有γ(P)(G)≤(「)n/4」。