论文题目: 图的控制数及其相关参数
论文类型: 博士论文
论文专业: 运筹学与控制论
作者: 单而芳
导师: 刘曾荣
关键词: 控制集,控制函数,匹配,中心,平衡点
文献来源: 上海大学
发表年度: 2005
论文摘要: 在过去的的三十年里,图论中发展最快的领域也许是图的“domination”的研究。这一研究领域出现快速发展的因素主要有三个:（一） 它在现实世界和诸如“覆盖”“位置确定”类数学问题中广泛而深刻的应用。例如目前编码理论中正在研究的码长为n覆盖半径为r的二进制码的最小数K（n,r）正是图的控制集理论中超立方图的r-距离控制数,显然,图论中的距离控制数更具有一般意义。现在,人们已发现图的控制集理论可广泛应用于编码理论,计算机科学,通信网络,监视系统和社会网络等理论与实践中。（二） 控制参数定义类型的多样性。根据实际背景的不同,现已定义的控制参数有几十种之多,而且随着研究的深入和应用的激发,新的参数如雨后春笋,不断涌现。（三） 图的控制参数确定问题的NP-完全性与其它组合优化中NP-完全问题紧密而自然的关系。在特殊图（如弦图,圆弧图,区间图,AT-free图等）上,寻找各类控制参数的多项式时间算法已成为组合优化领域中一个引人入胜而富有挑战性的研究方向。 本文所做工作主要包括以下四个部分:（1） 几类控制参数界的确定及与相关图参数的关系;（2） 极图的结构性质;（3） 函数控制数的界的确定;（4） 图的中心和平衡点问题。 在第二章,我们讨论了经典控制数的界和极图的刻画问题,主要做了以下几个方面的工作: 1993年,Reed[70]利用“路覆盖”技术证明了最小度至少为3的n阶图其控制数γ（G）不超过3/8n。我们通过改进这一技术进一步强化了上述结论,证明了最小度至少为2的n阶图其控制数,γ（G）不超过（3n+|V2|）/8,这里V2是图中度数为2的点的数目。作为这一结果的应用,证明了最小度至少为3的n阶图其k-限制控制数γk（G,γ）≤（3n+5k+3）/8（有关结果已投《Discrete Mathematices》）。 对任意连通图G,控制数、匹配数和覆盖数满足不等关系:γ（G）≤β（G）≤α（G）。我们首先证明了当γ（G）=β（G）时,G的最小度一定不超过2,进一步对γ（G）=β（G）且δ（G）=2的图给出了完全刻画（有关结果已被《数学进展》录用）。其次,对最小度为1的几类特殊图也给出了刻画。 尽管已知道当图的最小度小于3时,图的全控制数γt与匹配数β不可比较（见文[80]）,但我们证明了下列重要结论:对任意最小度不小于4的无爪图G,有γt（G）≤β（G）成立。进一步我们猜测对最小度为3的任意图这一结论成立。注意到事实β（G）≤|V（G）|/2,因此上述结果部分证明了由Favaron提出的关于全控制数猜想:γt（G）≤|V（G）|/2。
论文目录:
§1 引言
§2 图的控制数的上界
§2.1 基本概念和记号
§2.2 最小度为2的图的控制集和限制控制集
§2.3 匹配数与控制数相等的图
§2.3.1 预备定理
§2.3.2 最小度为2的图的结构性质
§2.3.3 匹配数与控制数相等的特殊图类
§2.4 图的匹配数与全控制数的关系
§2.5 图的k-控制数的Nordhaus-Gaddum型不等式
§3 图的配对控制数(Paired-domination number)
§3.1 配对控制数等于点数的2／3的极图刻画
§3.2 全控制数与配对控制数相等的树的结构
§3.2.1 (γt，γp)-树的刻画
§3.2.2 (γp，2β)-树的刻画
§3.3 图的配对控制数与其补图的色数
§4 图的函数控制数(Function domination number)
§4.1 图的函数控制数的基本概念
§4.2 偶图的负控制数的下界
§4.3 图的k-符号控制数的下界
§4.4 图的符号2-独立数的上界
§4.4.1 任意图符号2-独立数的上界
§4.4.2 多部图符号2-独立数的上界
§5 图的中心与平衡点集
§5.1 定义、记号与基本结果
§5.2 图的k-中心
§5.3 树的平衡点
参考文献
附录:
致谢
发布时间: 2005-09-16
参考文献
- [1].控制数与拓扑指数的研究[D]. 裴利丹.安徽大学2018
- [2].2-设计的自同构群、度量维度以及控制数[D]. 唐浪.华南理工大学2018
- [3].Graph Theoretical Studies on Reliability of Networks and Minimum Broadcast Graphs[D]. 吕长虹.南京大学2000
- [4].几类图的控制参数的理论与算法[D]. 赵敏.上海大学2006
- [5].图的邻域全控制数研究[D]. 王侃.华东师范大学2016
- [6].图的几类控制参数研究[D]. 蒋红星.上海大学2009
- [7].图的某些控制参数的计算[D]. 赵衍才.上海大学2011
- [8].图的配对控制数和彩虹控制数研究[D]. 王超.华东师范大学2015
- [9].关于图的若干参数的研究[D]. 宁文杰.清华大学2015
- [10].图的稳定性的相关研究[D]. 曹永昌.中国科学技术大学2009
相关论文
- [1].图的控制集的一些相关问题的研究[D]. 彭茂.上海交通大学2008
- [2].图的几类控制参数研究[D]. 蒋红星.上海大学2009
- [3].图的控制理论研究[D]. 陆由.中国科学技术大学2010
- [4].图的控制问题研究[D]. 李宁.中国科学技术大学2011
- [5].不同系统的混沌同步及相关问题的研究[D]. 陈骏.上海大学2004
- [6].图的交叉数等图论难题的研究[D]. 林晓惠.大连理工大学2004
- [7].关于图的因子与分数因子的若干结果[D]. 卞秋菊.山东大学2005
- [8].拟阵与图[D]. 李乐学.山东大学2005
- [9].几类图的控制参数的理论与算法[D]. 赵敏.上海大学2006
- [10].图的控制稳定性研究[D]. 黄佳.中国科学技术大学2007