图的控制集的一些相关问题的研究
本文关键词：无线传感器网络能效优先通信技术研究，由笔耕文化传播整理发布。
《上海交通大学》 2008年
图的控制集的一些相关问题的研究
彭茂
【摘要】： 控制集是图论中的重要概念,它定义为图中的一个点集,使得图中其它任何一点都与该点集中的某点相邻.这一概念的提出始于Konig、Berge和Ore,他们的著作和Cockayne, Hedetniemi,以及Larskar和Walikar等人的文章为后来的研究者提供了有益的启示. 在过去的30多年里,对图的各类控制集参数问题以及控制参数与图的其他参数的关系问题的研究已经成为图论研究的一个重要领域.在此期间,各种新的控制参数被不断提出,如具有“连通性”的控制集,具有“距离控制性”的控制集,具有“无赘性”的控制集等等,本文在连通控制集和距离控制集的基础上引入一种新的控制集–“[r,R]-控制集”,并从算法的角度来讨论它的性质. 如何寻找图的最小控制集是一个NP困难问题,它不能通过回溯法或随机化算法有效地解决,在这种情况下,对于其中的一些问题,代之以设计近似算法,我们要保证它是一个多项式时间算法,并且能得到一个近似于最优解的“合理”的解.对于最小化问题,算法的近似解与最优解的比值称为算法的近似比.近似比与1越靠近,算法所得的解就与最优解越接近.遗憾的是,并不是所有问题都能找到近似比为常数的近似算法,比如,已经证明:在P = NP的前提下,最小控制集问题就不可能找到比O(lnn)更好的算法. 在本文第二章中,我们首先引入了[r,R]-控制集的准确定义,然后对一般图中的最小[r,R]-控制集问题提出了一个近似比为lnΔ_r + [(2r+1)/R]-1的算法,这已经与O(lnn)同阶,可以认为,在一般图中,其改进的余地已经很小.然后我们分别考虑图的[r,R]-控制数与图的大小的关系、图的[r,R]-控制数与其补图的[r,R]-控制数的关系、图的[r,R]-控制集与全控制集的关系,得到了图的[r,R]-控制数的三个不同上界. 在第三章,我们从实际应用出发,将最小[r,R]-控制集限定在单位圆盘图中,考虑单位圆盘图中的特殊几何结构,得到了近似比为[4r(r + 1)(1 - (2θ-sin(2θ)/π)][(r+1)/R](常数)的算法,其中θ= arccos 2rR+1.在r,R取特殊参数的情况下,对算法的近似比进行了更细致的刻划. 在第四章,我们将最小[r,R]-控制集限定在随机正则图中,利用极大独立集给出了一个随机算法,并通过微分方程的方法分析了算法的返回值,进而得到了正则图中最小[r,R]-控制集的渐近界,并且证明,在r足够大的时候,最小[r,r + 1]-控制集的渐近界不超过d d/((d - 2)(d - 1)~(d/(d-2)).在对随机算法进行分析的过程中,我们指出了一篇主要参考文献在数据处理上的错误. 最后,我们给出对未来工作的展望作为结尾.
【关键词】：
【学位授予单位】：上海交通大学
【学位级别】：博士
【学位授予年份】：2008
【分类号】：O157.5
【目录】：
下载全文 更多同类文献
CAJ全文下载
(如何获取全文？ 欢迎：购买知网充值卡、在线充值、在线咨询)
CAJViewer阅读器支持CAJ、PDF文件格式
【共引文献】
中国期刊全文数据库 前10条
1 陈冬松;刘治国;王光兴;;移动Ad-hoc网络管理中基于节点定位的簇生成算法[J];兵工学报;2007年10期
2 丁立军;刘凯;李汉涛;张军;;自组织网络中UPMA协议的群间仿真[J];北京航空航天大学学报;2006年03期
3 薛楠;周贤伟;周健;;认知无线电网络自私行为问题及安全解决方案[J];北京科技大学学报;2009年09期
4 王海涛;移动Ad hoc网络的分簇算法及性能比较[J];北京邮电大学学报;2004年01期
5 薛钰;曾志民;郭义武;郭彩丽;;认知无线电中基于相似性的自适应分簇算法[J];北京邮电大学学报;2008年03期
6 王海涛;分簇结构在Ad Hoc网络中的应用综述[J];重庆邮电学院学报(自然科学版);2003年04期
7 王海涛,李桂伦;Adhoc网络中骨干网的建立和维护[J];重庆邮电学院学报(自然科学版);2005年01期
8 王琳珠;范亚芹;胡可刚;;基于Ad Hoc的有效广播路由算法[J];吉林大学学报(信息科学版);2009年01期
9 张静,孙雨耕,房朝晖;能量有效的最小连通支配集近似算法[J];传感技术学报;2004年04期
10 郑婵;尹令;孙世新;;无线传感器网络中d-Hop 2-连通容错支配集的分布式构造算法[J];传感技术学报;2012年05期
中国重要会议论文全文数据库 前10条
1 张强;夏艳;龚正虎;;一种基于信誉评估与能量辅助约束的混合MANET分簇协议[A];第八届全国信息隐藏与多媒体安全学术大会湖南省计算机学会第十一届学术年会论文集[C];2009年
2 赵光胜;王晓东;刘权;国文成;;混合式MANET中一种基于虚拟认证者的接入认证系统[A];第18届全国多媒体学术会议（NCMT2009）、第5届全国人机交互学术会议（CHCI2009）、第5届全国普适计算学术会议（PCC2009）论文集[C];2009年
3 王瑜;孟涛;相敬林;夏靖波;;一种应用于Ad hoc网络管理的分簇算法[A];2005中国控制与决策学术年会论文集（下）[C];2005年
4 包永平;任亚萍;;无线自组织网网络分群算法研究[A];2007通信理论与技术新发展——第十二届全国青年通信学术会议论文集（下册）[C];2007年
5 ;SLID: A Secure Lowest-ID Clustering Algorithm[A];Proceedings of the 1st Chinese Conference on Trusted Computing and Information Security[C];2004年
6 赵宁;;军用自组织网络体系结构研究[A];开创新世纪的通信技术——第七届全国青年通信学术会议论文集[C];2001年
7 王海涛;张学平;;Ad Hoc网络中骨干网的建立和维护[A];现代通信理论与信号处理进展——2003年通信理论与信号处理年会论文集[C];2003年
8 李汉涛;刘凯;张军;;高动态自组织网络中的高效多址接入协议[A];2005通信理论与技术新进展——第十届全国青年通信学术会议论文集[C];2005年
9 包永平;刘作学;;无线自组织网的网络分群算法研究[A];四川省通信学会2005年学术年会论文集[C];2005年
10 陈太尚;;一种基于认知无线电的组合加权分簇算法[A];2009年全国无线电应用与管理学术会议论文集[C];2009年
中国博士学位论文全文数据库 前10条
1 李青;无线移动自组网MAC关键技术研究[D];解放军信息工程大学;2009年
2 王伟;无线传感器网络若干关键技术研究[D];华中科技大学;2011年
3 赵楠楠;无线传感器网络拓扑控制算法研究[D];北京邮电大学;2011年
4 杨凯;无线Mesh网络高性能路由协议研究[D];西安电子科技大学;2011年
5 马闯;无线传感器网络容错关键技术研究[D];哈尔滨工业大学;2011年
6 王旭东;基于图论的智能电网最优孤岛划分模型和算法[D];天津大学;2011年
7 石胜林;基于无线Mesh网QoS关键技术研究[D];华中科技大学;2011年
8 掌明;无线传感器网络能效优先通信技术研究[D];南京邮电大学;2011年
9 陈育斌;高速分组无线网关键技术研究[D];西安电子科技大学;2000年
10 张文柱;无线Ad Hoc网络中若干关键技术研究[D];西安电子科技大学;2003年
中国硕士学位论文全文数据库 前10条
1 黄江;Ad Hoc网络分簇路由协议的研究与优化[D];南昌大学;2010年
2 潘霞;能量有效的无线传感器网络分群路由协议的研究与实现[D];解放军信息工程大学;2010年
3 靳超;战术自组网的分群与连通性问题的研究[D];东华大学;2011年
4 李云红;无线传感器网络能量均衡路由算法研究[D];西安电子科技大学;2011年
5 石玲玲;Ad Hoc网络证书撤销机制的分析和研究[D];西安电子科技大学;2011年
6 赵金辉;小区PHS系统深度覆盖设计[D];西安电子科技大学;2008年
7 杨东东;Ad Hoc网络中广播算法的研究[D];吉林大学;2011年
8 于亮亮;智能用电小区无线自组织网络方案设计[D];华北电力大学（北京）;2011年
9 王楠楠;无线网络中基于CDS的拓扑控制算法研究[D];曲阜师范大学;2011年
10 高永康;VANET路由及路由安全研究[D];北京邮电大学;2011年
【相似文献】
中国期刊全文数据库 前10条
1 罗永萍;杨爱民;;有向路和有向圈的控制集数[J];高等学校计算数学学报;2007年01期
2 张忠辅,张建勋;若干图参数的关系[J];科学通报;1990年16期
3 闫庆旭;一类控制系统的控制集和最优控制[J];烟台大学学报(自然科学与工程版);1990年02期
4 陈卫东,孟小华;求图控制集问题的模拟退火算法的改进[J];重庆师范大学学报(自然科学版);2004年02期
5 陈宏宇;牛翠霞;邹青松;;树的k-分支限制控制数的一个下界[J];山东大学学报(理学版);2010年02期
6 孙天川,赵敏,康丽英;循环图及单圈图的有效控制集与完美控制集[J];上海大学学报(自然科学版);2004年05期
7 王璐;刘展鸿;熊黎明;;一类含有两个分支2-因子的无爪图[J];江西教育学院学报;2007年03期
8 徐保根;罗茜;丁宗鹏;;关于图的集控制数[J];华东交通大学学报;2011年05期
9 阿勇嘎,斯钦;图的临界控制集与优控制集[J];宝鸡文理学院学报(自然科学版);2004年04期
10 齐登记,梁希泉;关于图的控制数Vizing's定理的推广[J];东北师大学报(自然科学版);2005年01期
中国重要会议论文全文数据库 前10条
1 沈志君;;欧盟、美国、英国及中国反垄断法立法目的及客体异同初探[A];2009中华全国律师协会知识产权专业委员会年会暨中国律师知识产权高层论坛论文集（下）[C];2009年
2 许立俭;韩崇昭;万百五;;工业过程稳态优化控制ISOPE算法的鲁棒性初探[A];1992年中国控制与决策学术年会论文集[C];1992年
3 张勤照;张文武;杨清;高德欣;;青钢小型一厂泵房电气智能集中管控系统设计[A];全国冶金自动化信息网2009年会论文集[C];2009年
4 宋献中;李源;;持股相近型公司大股东的监督与联盟行为——基于中国上市公司的研究[A];中国会计学会2006年学术年会论文集（中册）[C];2006年
5 赵文荣;侯学章;朱广田;;关于双线性分布参数系统的一类最优控制[A];1994年中国控制会议论文集[C];1994年
6 陈奕琳;马树萍;程兆林;;线性奇异系统的二次指标最优控制问题[A];1996年中国控制会议论文集[C];1996年
7 陶刚;张冬;;传媒集团财务系统远程接入的实现[A];中国新闻技术工作者联合会2008年学术年会论文集（上）[C];2008年
8 王琦;秦军;杨水陆;;乐滩水电站洪水系列一致性评价[A];中国水力发电工程学会水文泥沙专业委员会第七届学术讨论会论文集（下册）[C];2007年
9 邢科义;胡保生;陈浩勋;;受控Petri网的极大允许状态反馈控制律的综合算法[A];1993中国控制与决策学术年会论文集[C];1993年
10 王新;李燕萍;袁兵;;基于回路的无线自组网的拓扑发现和路由管理[A];科技、工程与经济社会协调发展——中国科协第五届青年学术年会论文集[C];2004年
中国重要报纸全文数据库 前10条
1 赛迪顾问通信产业研究中心副总经理 杨凯;[N];通信产业报;2007年
2 本报记者 次仁罗布;[N];山南报(汉);2006年
3 蒋少龙;[N];证券时报;2007年
4 常虹;[N];中国工业报;2004年
5 ;[N];中国经营报;2003年
6 湖南省邵东职业中专 朱世民;[N];电子报;2006年
7 胡文佳;[N];中国企业报;2003年
8 韦巍 陈楫宝;[N];21世纪经济报道;2005年
9 屈连志 记者 高靖峰;[N];锦州日报;2007年
10 本报记者 凌云峰;[N];上海证券报;2008年
中国博士学位论文全文数据库 前10条
1 陈磊;图中配对控制集问题的机械化算法研究[D];华东师范大学;2010年
2 李宪越;关于一些网络最优化问题的近似算法的研究[D];兰州大学;2009年
3 刘清海;几类组合优化问题的算法研究[D];新疆大学;2012年
4 陈星;几类图的连通性和控制集[D];新疆大学;2011年
5 胡夫涛;图的约束数研究[D];中国科学技术大学;2012年
6 蒋红星;图的几类控制参数研究[D];上海大学;2009年
7 单而芳;图的控制数及其相关参数[D];上海大学;2005年
8 陆由;图的控制理论研究[D];中国科学技术大学;2010年
9 董九英;图的彩虹连通数的若干上界[D];南开大学;2013年
10 赵衍才;图的某些控制参数的计算[D];上海大学;2011年
中国硕士学位论文全文数据库 前10条
1 秦敏艳;路和圈的定位控制集问题[D];华东师范大学;2010年
2 李业芳;无线传感器网络中连通控制集问题的研究[D];北京邮电大学;2010年
3 李秀英;求最小2连通r步控制集的两种算法[D];新疆大学;2011年
4 何永能;图的电力控制集问题[D];华东师范大学;2012年
5 盛斌;立方图的配对控制集问题上界[D];华东师范大学;2013年
6 吴亚娜;无爪图配对控制集问题上界的研究[D];华东师范大学;2013年
7 秦云龙;连通控制集的构造与维护算法研究[D];曲阜师范大学;2010年
8 吕杰;图中K-控制参数之间的一些关系[D];大连理工大学;2008年
9 罗永萍;几乎正则多部竞赛图的Hamilton性和有向图中几个计数问题[D];山西大学;2005年
10 邓婉婷;基于许可证的数字版权管理策略研究[D];华中科技大学;2006年
本文关键词：无线传感器网络能效优先通信技术研究，由笔耕文化传播整理发布。
，本文编号：162027
本文链接：https://www.wllwen.com/kejilunwen/wltx/162027.html
