树的罗马约束数研究

论文摘要

图的控制理论是图论中一个重要研究领域,在物理学,计算机科学,信息学,化学等很多学科有重要的应用.设图G=（V,E）且D（?）V,如果V-D中任一点都有D中的点与它相邻,则称D为G的控制集.图的最小控制集问题是NP-完备的,没有多项式时间算法去求解它.正是因为控制数的广泛应用且研究难度大,控制理论研究得到了极大的关注和快速的发展.根据实际应用,相应定义了不同的控制数.图的约束数是度量图控制脆弱性的参数,即边删除对控制数的影响,是度量图控制性能的参数.现实网络不是一成不变的,不但受到自然环境的影响,也容易遭受人为攻击,因此研究动态的网络模型是有意义的.本文主要研究的是图的罗马控制数对应的罗马约束数问题.罗马控制函数来源于Ian Stewart于1999年发表的论文[Defend the Roman Em-pire.Scientific American,281（1999）,136-139].转化成图论的语言,设G=（V,E）是一个非空简单无向图.定义图G上的罗马控制函数f:V→ {0,1,2}使得对任给的顶点u且f（uu）= 0至少存在一个顶点v且f（v）= 2与它相邻.实值函数f:V→R?的权记力w（f）=∑u∈ f（u）,简记为f（G）=w（f）.图G的罗马控制数是指图G的最小罗马控制函数的权值,用γR（G）表示.非空图G的罗马约束数是指删除最少边的数目使得得到的图的罗马控制数相比原来的变大,记为bR（G）.本文考虑的是其中一种简单不含圈的无向图,称为树,记作T,的罗马约束数问题.Rad和Volkmann在[Roman bondage in graphs,Discussiones Mathematicae Graph Theory,31（2011）,763-773]一文中介绍了罗马约束数问题.他们证明了树的罗马约束数不大于3.文末他们提出了如下问题:刻画罗马约束数分别为1,2,3的树.在本篇论文中,我们给出了罗马约束数为1的树的刻画,讨论了罗马约束数为3的树.

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
•   1.1 图论的由来和发展过程
•   1.2 关于图论的基本概念
•   1.3 控制数和约束数的概念
•   1.4 本文的研究成果
• 第二章 罗马控制函数的概念及一些已知结果
•   2.1 罗马控制函数的概念
•   2.2 一些已知的结果
• 第三章 罗马约束数为1的树
•   3.1 预备知识
•   3.2 初步结果
•   3.3 主要结果
• 第四章 总结与展望
•   4.1 总结
•   4.2 展望
• 参考文献
• 攻读硕士学位期间的学术活动及科研成果
• 致谢

文章来源

类型: 硕士论文

作者: 王兴伟

导师: 胡夫涛

关键词: 罗马控制函数,罗马约束数

来源: 安徽大学

年度: 2019

分类: 基础科学

专业: 数学,数学

单位: 安徽大学

分类号: O157.5;O231

总页数: 40

文件大小: 1689K

下载量: 15