图的目标集选取

《图的目标集选取》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。

1、万方数据㈣J『J『

2、川

3、fJJ

4、川川川洲川㈣JfY3303796学校编码：10384分类号——密级——居，1六芗博士学位论文图的目标集选取姜海宁指导教师姓名：钱建国教授专业名称：应用数学论文提交日期：2017年月论文答辩时间：2017年月学位授予日期：2017年月答辩委员会主席：蕴竖盈fU＼评阅人：——万方数据D。ct。ralDissertati。n、～Y33—0～37～96fllllllllllllfllJIIJllJlIJIf[[[一rff—rllTargetSetSelectiononGraphsByHainingJiangSupervisor：Profes

5、sorJianguoQianSpeciality：AppliedMathematicsInstitution：SchoolofMathematicalSciencesXiamenUniversityXiamen．P．R。China术，2017万方数据厦门大学学位论文原创性声明本人呈交的学位论文是本人在导师指导下，独立完成的研究成果。本人在论文写作中参考其他个人或集体己经发表的研究成果，均在文中以适当方式明确标明，并符合法律规范和《厦门大学研究生学术活动规范(试行)》。另外，该学位论文为()课题(组)的研究成果，获得()课题(组)经费或实验室的资助，在()实验室完成

6、。(请在以上括号内填写课题或课题组负责人或实验室名称，未有此项声明内容的，可以不作特别声明。)本人声明该学位论文不存在剽窃、抄袭等学术不端行为，并愿意承担因学术不端行为所带来的一切后果和法律责任。声明人(签名)：嬲指导教师(签名)：土o／7年细／oH万方数据厦门大学学位论文著作权使用声明本人同意厦门大学根据《中华人民共和国学位条例暂行实施办法》等规定保留和使用此学位论文，并向主管部门或其指定机构送交学位论文(包括纸质版和电子版)，允许学位论文进入厦门大学图书馆及其数据库被查阅、借阅。本人同意厦门大学将学位论文加入全国博士、硕士学位论文共建单位数据库进行检索，将学位

7、论文的标题和摘要汇编出版，采用影印、缩印或者其它方式合理复制学位论文。本学位论文属于：()1．经厦门大学保密委员会审查核定的保密学位论文，于年月日解密，解密后适用上述授权。()2．不保密，适用上述授权。(请在以上相应括号内打“√”或填上相应内容。保密学位论文应是已经厦门大学保密委员会审定过的学位论文，未经厦门大学保密委员会审定的学位论文均为公开学位论文。此声明栏不填写的，默认为公开学位论文，均适用上述授权。)声明人(签名)：粥zq}7年々月／OB万方数据厦门大学博士学位论文图的目标集选取摘要目标集选取问题(TSS)最初是由Kempe等提出的，用于研究信息、思想或影

8、响在社交网络上的传播．这类模型因其在经济、社会、医药和计算机科学等方面的广泛应用而备受关注．在目标集选取问题的研究中，网络通常被抽象为一个无向图，且每个点都被赋予一个阈值函数目(u)：v(a)jN，其中v(a)是G的点集，N是整数集．G中的点通过一个动态过程被依次激活：在初始步骤，选择G的一个顶点子集J5『作为初始激活集，在步骤i(i>0)，G中未被激活的点遵行下面的原则激活：顺序更新规则：当一个未激活点有至少臼(u)个己激活邻点，则这个点被激活．一旦这个点被激活，则在整个过程中保持激活状态．如果S通过激活过程激活了G中所有的点，则称S是G的0一目标集．目标集选取

9、问题的目标是选取基数最小的0一目标集S，其基数称为G的0一目标数，记为mino(G)．在目标集选取问题中，为了满足某些特殊需要设定了各种类型的阈值函数．特别地，当阈值函数目(u)=d(u)一1时，该问题与点反馈集问题(即，破圈集问题)有着密切的关系．已经证明目标集选取问题是NP一困难的(即使对于特殊的二部图)．因此，对该问题的研究主要集中在特殊图类，例如块状仙人掌图、弦图、哈明图、弦环、轮胎面、六边形网格、稀疏图、集团图、树、多部图和网格．论文共分六章：第一章给出了论文所涉及的基本概念和记号；介绍了研究背景及研究现状；最后介绍了本文的主要工作．第二章对满足mina

10、(G)=3的平面图进行一T一万方数据摘要了刻画，并证明这样的平面图的最小度最多是4．在第三章中，对于阈值函数k，我们给出了min忌(GDH)的上界，改进了Adams等的结果．特别地，对于尼=2，给出了紧的下界和更紧的上界．后者对于几乎所有在文献中已确定的卡氏积图都是可达的．在第四章和第五章中，我们对平面、柱状、环面及莫比乌斯型的四边形网格和三角形网格进行研究，其中阈值函数0=2，3、4．在最后一章中，我们先给出了零强制集与连通控制集之间的关系，并对Davila关于零强制集的猜想给出了一种证明方法．关键词：目标集选取；平面图；卡氏积；四边形网格；三角形网格；强制集一

11、II—万方