图的几类控制参数研究

论文摘要

图的控制数理论是图论的一个重要研究方向,也是发展最快的领域之一.图的控制理论研究不仅具有重要的理论意义,在计算机科学、通讯网络、编码理论、运筹学以及社会学等领域也具有广泛的应用.控制及其衍生出的控制已被广泛深入研究.本文研究了经典控制的三个衍生概念:全限制控制,全外连通控制及外连通控制.主要研究工作包括以下三个部分:在第二章中,我们讨论了全限制控制数的界和极图问题.由于一个图G存在全限制控制集,那么必有γtr（G）≤n或者n-2.首先,我们构造性刻画了全限制控制数为n的树、无爪图及一般图,也刻画了全限制控制数为n-2的树.然后,我们讨论了无爪图上全限制控制数.根据一个图的阶和最大度给出控制参数的界,这对许多其它控制参数已被建立.对全限制控制数,Henning等证明了:对最小度至少是2的连通图G,有γtr（G）≤n-△/2-1.如果限制在无爪图上,我们改进了这一结果并证明了:对最小度至少是2的连通无爪图G,有γtr（G）≤n-△+1,同时也刻画了取得这一界的极图.最后,我们讨论立方图上的全限制控制数.利用映射和分析方法,我们建立了立方图上全限制控制数的下界和上界并且构造性地刻画了达到下界的极图.如果限制在无爪立方图上,我们证明了全限制控制数与全控制数是相等的.从而导出一些对全控制成立的结论对全限制控制也同样成立.在第三章中,我们讨论全外连通控制数,这一概念最近由J.Cyman引入.我们建立了一个图和其补图的全外连通控制数的和的上界和下界（图论中也称之为Nordhaus-Gaddum-型不等式）并刻画了达到这些界的极图.在第四章中,我们根据提出新的控制参数的一般规律,自然地引入了外连通控制数的概念并讨论了其极图、界及复杂性.显然对任意一个图G,我们有γoc（G）≤n(这里γoc（G）是图G的外连通控制数).首先我们构造性刻画了外连通控制数等于n、n-1或n-2的极图,并且确定了一个图和其补图的外连通控制数的和的上界和下界.然后,我们讨论了外连通控制数在树上的情况,给出分别根据图的最大度和阶的两个下界并刻画了达到这两个下界的极树.我们也刻画了外连通控制数等于控制数的树.最后,我们证明了外连通控制数的判定问题是NP-完全的.

论文目录

• 摘要
• Abstract
• 第一章 绪论
• 1.1 图的控制数理论的研究背景
• 1.2 基本概念和记号
• 1.3 本文的主要工作
• 第二章 图的全限制控制数
• 2.1 问题的研究背景
• 2.2 一些具有较大全限制控制数的图的刻画
• tr（T）=n的树'>2.2.1 γ_tr（T）=n的树
• tr（T）=n-2的树'>2.2.2 γ_tr（T）=n-2的树
• tr（G）=n的图'>2.2.3 γ_tr（G）=n的图
• 2.3 无爪图上的全限制控制数
• 2.4 立方图上的全限制控制数
• 第三章 图的全外连通控制数
• 3.1 问题的研究背景
• 3.2 全外连通控制数的一个Nordhaus-Gaddum-型不等式
• 第四章 图的外连通控制数
• 4.1 具有较大外连通控制数的图
• 4.2 一个Nordhaus-Gaddum-型不等式
• oc的界'>4.3 在树上γ_oc的界
• oc)-树'>4.4 (γ,γ_oc)-树
• 4.5 外连通控制的复杂性结果
• 第五章 总结与展望
• 参考文献
• 攻读博士学位期间撰写论文情况
• 致谢