点可迁图的全约束数和有效全控制

发布时间：2020-11-17 13:28

　　 本篇论文,主要考虑的是非空简单图.通常所说的图即包含有向图也包含无向图,在图论中没有明确的规定图的符号.一般地,用G =(V,E)来表示图,其中V=V(G)表示图G的顶点集以及E= E(G)表示图G的边集.顶点对(u,v)表示的是从顶点u指向顶点v的一条有向边,注意当(u,v),(v,u)∈E时,则可把这两条有向边当成一条无向边,用uv表示.设图G是有向图,如果G的每条边(u,v)都有(v,u)∈E则图G就称为无向图.设D为图G的顶点子集,如果对于任意一个不在D当中的顶点v都有u ∈D使得(u,v)∈E,则称D为图G的控制集.图G的控制数是指最小控制集所含顶点的个数,通常用γ(G)来表示.设S为每个顶点入度大于零的图G的顶点子集,如果对于每一个顶点v ∈ V(G)都有u∈D使得(u,v)∈E,则称S为图G的全控制制集.图G的全控制数是指在最小全控制集所含有顶点数,通常用γ_t(G)来表示.图G的约束数是指删除G中最少边集的数目使得图G的控制数增加,用b(G)表示.图G的全约束数是指删除G中最少边集的数目使得图G的全控制数增加,用b_t(G)表示.在这篇论文中,我们建立了点可迁图的全约束数的一个紧的下界(通常下界比上界难很多),通过研究全约束数和有效全控制数之间的关系,我们也得到了正则图全约束数的一个上界.如果图有有效全控制集,在无向图情形下给出了紧的上下界,在有向图情况下,完全确定了全约束数的精确值.作为应用推广,我们也研究了一些循环图、哈拉里图、网格网络的运算,通过它们有效控制集存在的特征,研究得到它们的全约束数.另外对于一些特殊的图,例如超级立方体我们也得到了它的全约束数的上下界.实际应用中的图模型大都是点可迁图,论文取得的成果,加深了点可迁图在控制理论上的认识,在实际网络中的结果为人们在现实中应用这些网络提供了全控制容错性的参考.
【学位单位】：安徽大学
【学位级别】：硕士
【学位年份】：2018
【中图分类】：O157.5
【文章目录】：
摘要
ABSTRACT
第一章 绪论
    1.1 图论的由来和发展过程
    1.2 关于图论的基本概念
    1.3 控制数和约束数的概念
第二章 全约束数和有效全控制
    2.1 引言
    2.2 初步的结果
    2.3 主要的结果
第三章 循环图的全约束数和有效全控制集
    3.1 双环网络图的有效全控制集和全约束数的上下界
    3.2 Harary图的全约束数和有效全控制集
    3.3 其它的应用
第四章 总结与展望
    4.1 总结
    4.2 展望
参考文献
攻读硕士学位期间科研情况及学术活动
致谢

【相似文献】

相关期刊论文 前10条

1 李念祖;刘儒英;;非色唯一的连通顶点可迁图的广泛存在性[J];青海师范大学学报(自然科学版);2006年01期

2 欧见平,张福基;点可迁图中的正则因子(英文)[J];数学研究与评论;2004年03期

3 欧见平,张福基;点可迁图的顶点划分[J];厦门大学学报(自然科学版);2003年01期

4 郭大昌;吴传荣;;关于L.Lovase猜想[J];工业工程;1989年02期

5 邓汉元;关于连通点可迁图的色性[J];北京理工大学学报;1989年01期

6 李才恒;;距离可迁图在笛卡尔积下封闭的条件[J];云南师范大学学报(自然科学版);1989年02期

7 欧见平;;点可迁图的限制边连通性[J];数学物理学报;2005年06期

8 刘儒英;李念祖;;连通的顶点可迁图的色唯一性[J];应用数学;1991年02期

9 李念祖;刘念祖;刘儒英;;几类非色唯一的连通顶点可迁图[J];上海第二工业大学学报;2005年04期

10 王朝瑞,石民勇;点可迁图中的两个不相交的极大独立点集(英文)[J];北京理工大学学报;1991年03期

相关博士学位论文 前1条

1 洪振木;某些网络可靠性和有效性研究[D];中国科学技术大学;2014年

相关硕士学位论文 前4条

1 李露;点可迁图的全约束数和有效全控制[D];安徽大学;2018年

2 张国春;拟可迁图上渗流临界概率的唯一性[D];首都师范大学;2007年

3 王彦;一类与sierpi(?)ski地毯相关的拟可迁图上的渗流模型[D];首都师范大学;2007年

4 徐根玖;有向图中若干问题的研究[D];西北工业大学;2004年

本文编号：2887551