若干图类的全符号控制数的研究

发布时间：2017-07-20 08:14

  本文关键词：若干图类的全符号控制数的研究

  更多相关文章： 全符号控制数 笛卡尔乘积图 路径图 圈图

【摘要】：图的符号控制是图论的一个重要的研究方向,不仅仅在实际生活中有着非常广泛的应用,例如,发射基站的选址、计算机通讯网络和群决策等,而且人们也可以在计算的复杂性和算法设计、优化理论、通讯网络设计与分析等方面应用图的控制理论。我们研究图的符号控制尤其是一些特殊图的符号控制问题可以为解决一般的NP-困难问题提供重要的借鉴,具有较为重要的意义,图的控制数的研究也因此一直受到广大学者的关注。本文主要研究路径图Pm与圈图Cn的交图的全符号控制数。本文考虑的图G均为有限简单连通图,根据Pm□Cn的点和边邻域的特点(在全符号控制研究中,顶点的邻域中包含边,边的邻域中也包含顶点),给出图Pm□Cn的全符号控制数较好的上下界。首先,根据前人的重要结论,对于任意图G,如果图G顶点的最小度为δ(G),最大度为△(G),顶点数为|V(G)|,边数为|E(G)|,那么G的全符号控制数为：并且这个下界是可达的,其中ρ(s)表示s的奇偶性,即如果s是奇数时,则ρ(s)=奇数,如果s是偶数时,则ρ(s)=偶数。对于Pm□Cn,根据上式可以得到γs*(Pm□Cn)≥0,由于Pm□Cn的点和边邻域的特性,我们可知其全符号控制数γs*(Pm□Cn)的下界可以比零更大一些。利用解析法证明Pm□Cn的全符号控制数γs*(Pm□Cn)的下界,该下界比一般图G的全符号控制数γs*(G)的下界大。然后,利用计算机构造证明给出图Pm□Cn的全符号控制数较好的上界。基于Pm□Cn点和边邻域的特点,设计有效的分支限界条件,研制计算机算法,构造全符号控制函数,计算γs*(Pm□Cn)的上界。最终,我们给出图Pm□Cn的全符号控制数。
【关键词】：全符号控制数 笛卡尔乘积图 路径图 圈图
【学位授予单位】：大连海事大学
【学位级别】：硕士
【学位授予年份】：2016
【分类号】：O157.5
【目录】：

• 摘要5-7
• ABSTRACT7-11
• 第1章 绪论11-18
• 1.1 控制数问题的研究背景和意义11-14
• 1.1.1 研究背景11-13
• 1.1.2 研究意义13-14
• 1.2 国内外研究现状及发展动态14-17
• 1.2.1 图的符号(点)控制数14-15
• 1.2.2 图的符号边控制数15-16
• 1.2.3 图的全符号控制数16-17
• 1.3 本文主要工作与结构安排17-18
• 第2章 图的控制理论及其应用18-26
• 2.1 图的基本概念18-19
• 2.2 图的控制理论的基本概念与性质19-21
• 2.3 图的控制问题在实际中的应用21-26
• 2.3.1 安排考试时间问题22
• 2.3.2 计算机通讯问题22-23
• 2.3.3 选址问题23-24
• 2.3.4 群决策问题24
• 2.3.5 研究社会网络的结构和属性24-25
• 2.3.6 影响最大化问题25-26
• 第3章 路径与圈交图的全符号控制数研究26-43
• 3.1 路径与圈交图的相关概念26-27
• 3.1.1 路径图26
• 3.1.2 圈图26
• 3.1.3 笛卡尔乘积图26-27
• 3.2 路径与圈交图的相关结论27-28
• 3.2.1 点控制27
• 3.2.2 边控制27-28
• 3.2.3 全控制28
• 3.3 路径与圈交图的全符号控制数的界限28-43
• 3.3.1 路径与圈交图的全符号控制数的下界29-31
• 3.3.2 路与圈交图的全符号控制数的上界31-43
• 第4章 总结与展望43-45
• 4.1 总结43-44
• 4.2 本课题今后需要进一步研究的地方44-45
• 参考文献45-50
• 攻读硕士学位期间发表论文情况50-51
• 致谢51

【相似文献】

中国期刊全文数据库 前10条

1 徐保根;关于图的符号星控制数[J];华东交通大学学报;2004年04期

2 徐保根;关于n阶图的最小减控制数[J];华东交通大学学报;2005年02期

3 袁春华;刘坚;冯立华;;图的占优控制数与符号k-子控制数的几个界[J];安庆师范学院学报(自然科学版);2006年02期

4 熊坤;苏健基;;几类图的符号星控制数[J];广西科学;2007年03期

5 孙桂艳;乔永涛;;关于图的减控制数[J];曲阜师范大学学报(自然科学版);2008年04期

6 赵金凤;徐保根;赵华;帅春萍;;关于图的两类边控制数[J];华东交通大学学报;2008年05期

7 徐保根;李春华;;图的符号星k控制数[J];纯粹数学与应用数学;2009年04期

8 周仲旺;;偶阶完全图的点-边全符号控制数[J];应用数学学报;2010年01期

9 黄中升;;图的逆符号边全控制的性质[J];赤峰学院学报(自然科学版);2010年06期

10 李艳坡;高明晶;王宏丽;;图的负边全控制数[J];河北师范大学学报(自然科学版);2010年05期

中国重要报纸全文数据库 前10条

1 ;今一季度全市安全生产事故通报[N];汉中日报;2007年

2 记者 宋兰兰;我市首次晒“三公”经费[N];长江日报;2011年

3 粟时勇 记者　黄先明;“人员控制数”破终身制[N];四川日报;2006年

4 科讯;引进院士不计入结构比例控制数[N];广东科技报;2005年

5 记者 马晓芳;我区实行事业编制分类管理[N];宁夏日报;2009年

6 记者　吕玲;逾六成医疗费超标[N];福州日报;2006年

7 陈会扬;福建患者医药费用偏高[N];健康报;2006年

8 记者 车莉;去年我市“三公经费”支出3.33亿[N];长江日报;2012年

9 徐侃;把安全生产工作抓实抓细[N];安庆日报;2009年

10 陆天荣;车祸猛于虎[N];苏州日报;2006年

中国博士学位论文全文数据库 前8条

1 单而芳;图的控制数及其相关参数[D];上海大学;2005年

2 蒋红星;图的几类控制参数研究[D];上海大学;2009年

3 赵衍才;图的某些控制参数的计算[D];上海大学;2011年

4 李宁;图的控制问题研究[D];中国科学技术大学;2011年

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

6 吕长虹;[D];南京大学;2000年

7 赵敏;几类图的控制参数的理论与算法[D];上海大学;2006年

8 曹永昌;图的稳定性的相关研究[D];中国科学技术大学;2009年

中国硕士学位论文全文数据库 前10条

1 陈悦;图的几类K控制数[D];华东交通大学;2012年

2 孟弦;基于距离条件下的图参数与图结构研究[D];华中师范大学;2015年

3 杜娟;图的符号控制数[D];山西大学;2014年

4 张利贤;图的参数控制研究[D];浙江师范大学;2015年

5 黄海圆;笛卡尔乘积图的配对控制数[D];浙江师范大学;2015年

6 于涵;图的两种控制数中相关问题的研究[D];哈尔滨师范大学;2015年

7 曹惠萍;若干图类的全符号控制数的研究[D];大连海事大学;2016年

8 廖万生;图的减边控制数[D];暨南大学;2008年

9 崔玉燕;树的减边控制数[D];暨南大学;2009年

10 尹传勇;关于图的几类控制数的界[D];华中师范大学;2002年

，

本文编号：567019