点权值图的k-电力控制集问题的算法研究

发布时间：2020-04-22 00:30

【摘要】：图的电力控制集问题来源于电力网络系统中如何选择安排最少检测仪器的节点位置问题,电力控制集问题是控制集问题延伸出的一个重要研究分支。设G=(V,E)为一个简单图,s(?)V为一个顶点子集,若满足V\s中每个点都与S中至少一个点相邻,称S为图G的控制集,图G的控制数γ(G)是其控制集的最小基数,控制集问题就是确定图上控制数。S(?)V是图G的电力控制集,当且仅当V中每个点通过如下两种方式可以获得信息:(1)任意v∈ S,传递信息给其本身,同时也传递信息给其所有的邻居点;(2)一旦v获取到信息,且只有一个未获取信息的邻居点,则v传递信息给该邻居点。图G的电力控制数γ_p(G)为电力控制集的最小基数。电力控制集问题就是确定图上电力控制数。设k为非负整数,图G的k-电力控制集S的定义与电力控制集相似,仅将第二种获得信息方式更改为:一旦v获取到信息,并且v至多还有k个未获取信息的邻居点,则v传递信息给这些邻居点。图G的k-电力控制数γ_(kp)(G)为k-电力控制集的最小基数,k-电力控制集问题就是确定图上k-电力控制数。当k=0时,为控制集问题;当k=1时,为电力控制集问题。在实际电力网络系统操作中,由于不同节点设置监测仪器的成本存在差异,因此研究带权值图的电力控制集问题具有更强的现实意义。给定点权值图G=(V,E,w),w是定义在点上的权重,对于任意v ∈ V,w(v)≥0。图G的带权值k-电力控制数γkpw(G)=min {Σ_(v∈s) w(v)|S为G的一个kk-电力控制集}。本文对一些特殊图类上寻找带权值k-电力控制数有效算法进行了研究,主要工作包括以下几个部分:本文第一章介绍了控制集、电力控制集、带权值控制集类问题研究背景及现状。T.W.Haynes等人已经证明电力控制集问题在一般图上的NP-困难性,人们也探讨了一些特殊图类上各类控制集问题的多项式时间算法。在带权值的特殊图类上,各类控制集问题的算法也被大家所关注。本文第二章研究点权值树上k-电力控制集问题,以定理2.1的结论为基础,从树序列的顶点顺序出发,采用动态规划的技术给出了求解点权值树上k-电力控制数的线性时间算法,并且证明了该算法的正确性。本文第三章研究了点权值仙人掌图上k-电力控制集问题,定理3.1给出了求解点权值圈上k-电力控制集问题的理论方法。再以圈和树上的思想方法为基础,给出求解点权值仙人掌图上k-电力控制数的有效算法,算法复杂度为O(m + bn),其中m为边数,n为顶点数,b为图中的长度大于等于3的圈数,并证明了算法的正确性。
【图文】：

图(Cactus graph)。人掌图 G，有如下等价命题：通图 G 称为仙人掌图；通图 G 上任意两个长度大于等于 3 的圈，最多只有一个公通图 G 上每条边都至多在一个圈上。意的仙人掌图，其上的点都可以被分成下述三类[10]： 类顶点：只在一个圈上，且度为 2； 类顶点：不在任何一个圈上； 类顶点：至少在一个圈上，且度大于等于 3。2 左图给出了仙人掌图的一个示例，，及各顶点的类型。

图 1.3：三类图之间关系的概念之一，对于各类控制集问题，树一。Cockayne 等人[13]采用标号的方法ng[16]则采用动态规划的方式给出树上给出了树上电力控制集问题线性时间算制集问题线性时间算法；其他一些关于,29,35,40,42,45,52 等]。控制集问题的研究也得到学者们较多关,46,49,53 等]。
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】

相关期刊论文 前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];大连海事大学;2018年

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

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

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

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

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

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

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

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

相关硕士学位论文 前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年

本文编号：2635917