学位论文 > 优秀研究生学位论文题录展示

关于图的几类特殊控制的研究

作　者: 帅春萍
导　师: 徐保根
学　校: 华东交通大学
专　业: 运筹学与控制论
关键词: 符号边控制数减边控制数减圈控制数反减圈控制数符号圈点控制数
分类号: O157.5
类　型: 硕士论文
年　份: 2009年
下　载: 24次
引　用: 0次
阅　读: 论文下载

内容摘要

随着计算机技术的飞速发展,图论作为离散数学中的一个重要组成部分,也得到了高速的发展。图的控制理论是图论中的一个重要研究课题,根据实际背景的不同,如今已定义的控制参数有几十种之多,如从图的点控制到图的边控制,再到其它的各种特殊控制,从图的一般控制到符号控制、减控制,再到反符号控制,等。同时随着研究的深入和实际应用的需要,新的概念与新的参数将会不断涌现,由此将使得控制理论更加丰富和完善。图的控制理论不仅在图论本身的研究方向有着广泛应用,而且在其他的学科领域如计算机网络及其拓扑结构、通讯及交通、编码理论和社会网络等领域也有重要应用。本文在边控制问题上,着重研究四类控制问题,即符号边控制、减边控制、减圈控制和反减圈控制;在点控制问题上主要研究图的符号圈点控制,主要工作包括以下三方面:第一,图的符号边控制数首先是由徐保根教授于2001年提出的,之后又对其进行了推广。我们主要对符号边控制数的相应概念与性质、一般图控制数的界限以及特殊图的控制数作了总结与研究,并对其中的一些定理进行了证明。第二,我们在已有的减边控制和反减圈控制数概念的基础上,引入了图的减圈控制数概念与性质,主要给出了图的减圈控制数的下界,并确定了一些特殊图的减圈控制数,主要结果如下:用γm′c (G )表示图G的减圈控制数,则有1、对于任意n阶图G ,均有,当且仅当G为树时等号成立;2、对于任意n (n≥3)阶极大平面图G ,均有3、对于任意n≥3阶完全图K n,均有4、设n和m均为整数,且n≥3 ,m≥2,则( )5、设整数n≥3时,则n +1阶轮图W n +1 =Cn∨K1的减圈控数为:其中[x ]表示不超过x的最大整数;第三,在已有的符号圈控制数概念的基础上,提出了符号圈点控制数的概念,给出了一些相应的性质,得出了一般图的符号圈点控制数的界限,并且确定了几类特殊图的符号圈点控制数,主要结果如下:用γsc ( G)表示图G的符号圈点控制数,则有1、对于任意n阶极大可平面图G (n≥3),均有:(1)γsc (G )= n-2β(G); (2)γsc (G∨K1 )=n+10-2β(G),其中β(G)表示图G的点独立数;2、对于任意n阶图G,若其最小度δ=δ(G )≥2,则有γsc (G )≥2δ-n;3、设n和m均为整数,则(1)当n≥3时,γsc ( K n) = n- 2; (2)当n≥2, m≥2时, ( )γsc K n , m= m + n- 2; (3)当n≥3时,γsc ( Cn ) =当当n n为为奇偶数数时时; (4)对任意树T ,均有γsc (T ) =-V(G )。4、设整数n≥3,则n +1轮图W n +1 =Cn∨K1的符号圈点控制数当当nn为为偶奇数数时时;。

全文目录

摘要  4-6
ABSTRACT  6-9
主要符号说明  9-11
第一章绪论  11-20
  1.1 图的控制数理论产生、发展、应用与主要研究方向  11-12
  1.2 图论的基本概念及其使用的符号和术语  12-16
    1.2.1 图的同构，完全图，偶图，补图  13-14
    1.2.2 顶点的度，度序列，路和图的连通性  14-15
    1.2.3 子图和图的运算  15-16
  1.3 图的控制理论的国内外研究现状  16-18
  1.4 本文所做的主要工作  18-20
第二章图的符号边控制数  20-28
  2.1 一般边控制  20-23
  2.2 关于图的符号边控制  23-27
    2.2.1 符号边控制的概念和性质  23-24
    2.2.2 一般图的符号边控制  24-26
    2.2.3 特殊图的符号边控制  26-27
  2.3 小结  27-28
第三章减边控制  28-38
  3.1 减边控制概念和性质  28-29
  3.2 减边控制数的下界  29-31
  3.3 图的反减圈控制数和图的减圈控制数  31-37
    3.3.1 图的反减圈控制数和减圈控制数的定义及其性质  32-33
    3.3.2 反减圈控制数的上界和减圈控制数的下界  33-34
    3.3.3 特殊图的反减圈控制数和减圈控制数  34-37
  3.4 小结  37-38
第四章图的符号圈控制和符号圈点控制  38-51
  4.1 图的符号圈控制  39-45
    4.1.1 关于图的符号圈控制的相关概念和性质  39-41
    4.1.2 一般图的符号圈控制数  41-44
    4.1.3 特殊图的符号圈控制数  44-45
  4.2 符号圈点控制数  45-49
    4.2.1 符号圈点控制数的定义和性质  45-46
    4.2.2 主要结果及其证明  46-49
  4.3 小结  49-51
第五章总结  51-52
  5.1 主要工作回顾  51
  5.2 本课题今后需进一步研究的地方  51-52
参考文献  52-55
个人简历在读期间发表的学术论文  55-56
致谢  56

关于图的几类特殊控制的研究

内容摘要

全文目录

相似论文