关于图的几类控制数的下界的研究

摘要

对于图G=(V,E)，子集S包含于V，称点集S为图G的控制集，若对于任意的y∈V-S，都存在x∈S，使xy∈E(G)。
　　由于控制理论的研究越来越引起人们的重视，人们对控制数有了更深的了解，提出了不同的控制数。例如：符号控制数，符号边控制数，符号全控制数等。这些控制数在图的结构中起了重要的作用。
　　本论文主要讨论了图的几类控制数的下界。在[3]中，鲁进步，刘林中给出了全符号控制函数的定义，并给出了一些特殊图的全符号控制数的上界。本文继续研究图的全符号控制数，并且得到一些特殊图的全符号控制数的下界，接着又给出了一般图的全符号控制数的下界。
　　本文还给出了图的负边控制的定义：设为一个图，一个函数f:E→{-1, 0,1}被称为图G的一个负边控制函数，如果G f[e]=f(N[e])=∑x∈N[e]f(x)≥1对所有的边e∈E成立。图的负边控制数定义为：γ-e(G)=min{f(E)｜f为图G的负边控制函数}。并讨论了图的负边控制数的下界，还刻画了γ-e(G)=｜E(G)｜的图。
　　最后本文研究了路的符号边控制数的界，即给出了m+4/3≤γse(Pn)≤m+8/3。

目录

封面

声明

中文摘要

英文摘要

目录

1 绪 论

1.1 图的控制数的研究背景及现实意义

1.2 图的控制数的发展状况

1.3 基本概念及常用符号

1.4 本文的主要内容及章节安排

2 图的全符号控制数的下界

2.1 基本概念

2.2 一些特殊图类的全符号控制数的下界

2.3 一般图类的全符号控制数的下界

3 图的负边控制

3.1 负边控制的定义

3.2 图的负边控制数的下界

3.3 负边控制数与边数相等的图

4 路的符号边控制数的界

4.1 基本概念

4.2 主要结果

结束语

致谢

参考文献

攻读硕士阶段所完成的论文