图的配对控制集问题和电力控制集问题的研究

发布时间：2020-08-17 10:01

【摘要】：控制集是图论的一个重要概念,它是指图中的一个点集,使得图中其它任何一点在该点集都至少有一个邻点.图的配对控制集问题和电力控制集问题是两类重要的控制集问题.本文对这两类控制集问题展开研究.设图G =(V,E)为无孤立顶点的简单图.S(?)V是G的一个配对控制集当且仅当V\S中每个顶点都与S中某点相邻,并旦G[S]有完美匹配.图G的配对控制数,记γpr(G),定义为min{|S|| S为G的配对控制集}.设图G =(V,E)为简单图.S(?)V是G的一个电力控制集当且仅当V中所有的点可以通过下面两种方式获得信息:(1)如果v ∈ S,那么v传递信息给自己和所有的邻点.(2)如果一个有信息的点υ仅有唯一一个邻点u没有信息,那么v传递信息给u.图G的电力控制数,记γp(G),定义为min{|S|| S为G的电力控制集}.k-电力控制集问题是电力控制集问题的自然推广.设图G =(V,E)为简单图,k是非负整数.S(?)V是G的一个k-电力控制集当且仅当V中所有的点可以通过下面两种方式获得信息:(1)如果v ∈ S,那么v传递信息给自己和所有的邻点.(2)如果一个有信息的点v至多有k个邻点没有信息,那么v传递信息给自己所有没有信息的邻点.类似地,图G的k-电力控制数,记γp,k(G),定义为min{|S|| S为G的k-电力控制集}.当k = 0时,k-电力控制集问题就是控制集问题.当k = 1时,k-电力控制集问题就是电力控制集问题.在图的控制集问题的研究中,确定控制数的上界是一个主流研究方向,无爪图是图论研究的重要图类.本文第一章介绍配对控制集问题和电力控制集问题的背景和研究现状.在第二章和第三章,我们分别对无爪图的配对控制数和电力控制数的上界进行了探讨.Goddard和Henning在2009年提出猜想:令G(?)P是一个n阶连通图,在这里P表示Petersen图.若δ(G)≥3,则γpr(G)≤4n/7.这是配对控制数上界研究的一个重要猜想.本文第二章对无爪图的配对控制集问题展开研究.我们证明了:令G是一个n阶无爪图,若δ(G)≥ 4,则γpr(G)≤n/2 并且这个上界是可达的(见定理2.1.1).该结果改进了 Cao和Shan等人2016年的结果.Dorbec等人在2013年提出猜想:令G =(V,E)是一个n阶r-正则连通图,其中≥ 1,r ≥ 3.若G(?)Kr,r,则γp,k(G)≤n/r+1,其中Kr,r是完全二部图.Dorbec等人证明了该猜想对k = 1,r = 3的情形成立.在本文第三章中,我们首先找到一系列r-正则无爪图(r ≥ 4为偶数)作为反例,部分否定了 Dorbec等人的猜想.然后,我们研究4-正则无爪图的电力控制数的上界,证明了:若G =(V,E)是一个n阶4-正则连通无爪图,则γp(G)≤n+1/5,并且这个上界是可达的(见定理3.1.1).
【学位授予单位】：华东师范大学
【学位级别】：博士
【学位授予年份】：2018
【分类号】：O157.5
【图文】：

图 1: 棋盘本专著 [50, 52], 专著中较为系统地阐述了有关图的控图控制集的定义. 是图 的顶点集的一个子集, 对每个 中的点和 相邻, 则称 是 的一个控制集.图 = ( , ) 的一个控制集有如下等价定义: 对于每个 ∈ ;中的点 , | [ ] ∩ | ≥ 1; 中的点 , | ( ) ∩ | ≥ 1.果 是图 的一个控制集, 那么任意点集 ′ 也是

【相似文献】

相关期刊论文 前10条

1 苏亚娟;;超图的连通边控制集问题一个贪婪算法[J];现代商贸工业;2012年18期

2 马文凯;李德英;张昭;;构建最小k重控制集的概率算法[J];中国科学:数学;2011年08期

3 李建平;刘旭;朱娟萍;;赋权树状网络中r-控制集问题和k-中心问题[J];运筹学学报;2009年02期

4 罗永萍;杨爱民;;有向路和有向圈的控制集数[J];高等学校计算数学学报;2007年01期

5 皮军德;林浩;;直线簇上区间图的最小全控制集和最小配对控制集[J];河南科学;2007年04期

6 王光源;方奇志;;k-控制集对策[J];中国海洋大学学报(自然科学版);2006年S2期

7 阿勇嘎,斯钦;图的临界控制集与优控制集[J];宝鸡文理学院学报(自然科学版);2004年04期

8 陈方淦,孙良;平面图选择控制集问题的复杂性分析及算法设计[J];北京理工大学学报;2003年03期

9 王春香,毛经中,陈晶晶;关于边控制集的一些结论[J];华中师范大学学报(自然科学版);2002年02期

10 于崇智;关于集控制集的若干结论[J];华东交通大学学报;1997年01期

相关重要报纸文章 前2条

1 宦建新　通讯员　沈维强;浙江“食品安全科技专项”取得成果[N];科技日报;2005年

2 石家庄市畜牧水产局 赵洪明　强慧勤 王荣申 张涛 李钊;养殖投入品控制集成技术[N];河北科技报;2013年

相关博士学位论文 前10条

1 毛睿;图的配对控制集问题和电力控制集问题的研究[D];华东师范大学;2018年

2 陈磊;图中配对控制集问题的机械化算法研究[D];华东师范大学;2010年

3 黄佳;图的控制稳定性研究[D];中国科学技术大学;2007年

4 刘清海;几类组合优化问题的算法研究[D];新疆大学;2012年

5 陈星;几类图的连通性和控制集[D];新疆大学;2011年

6 李宪越;关于一些网络最优化问题的近似算法的研究[D];兰州大学;2009年

7 赵维胜;关于树的控制问题与强乘积图约束数的研究[D];兰州大学;2015年

8 胡夫涛;图的约束数研究[D];中国科学技术大学;2012年

9 陆由;图的控制理论研究[D];中国科学技术大学;2010年

10 王超;图的配对控制数和彩虹控制数研究[D];华东师范大学;2015年

相关硕士学位论文 前10条

1 周瑜;点权值图的k-电力控制集问题的算法研究[D];华东师范大学;2018年

2 于俊英;阿基米德铺砌图中定位控制集的研究[D];河北师范大学;2018年

3 赵利芬;关于图的控制集划分[D];华东交通大学;2015年

4 李秀英;求最小2连通r步控制集的两种算法[D];新疆大学;2011年

5 罗传文;无线网络中连通控制集的算法设计与分析[D];曲阜师范大学;2016年

6 秦云龙;连通控制集的构造与维护算法研究[D];曲阜师范大学;2010年

7 陈春霞;关于路和圈的验证码和定位控制集问题[D];华东师范大学;2009年

8 盛斌;立方图的配对控制集问题上界[D];华东师范大学;2013年

9 丁玲玲;图的控制集问题的近似算法研究[D];中国海洋大学;2008年

10 何永能;图的电力控制集问题[D];华东师范大学;2012年

本文编号：2795179