谢尔宾斯基相关图类的结构性质

谢尔宾斯基相关图类的结构性质

作者:师大云端图书馆 时间:2015-07-22 分类:期刊论文 喜欢:2969
师大云端图书馆

【摘要】图论的产生最早可追溯到十八世纪三十年代,其标志性事件是瑞士数学家莱昂哈德.欧拉(LeonhardEuler,1707年4月15日-1783年9月18日)解决了哥尼斯堡七桥问题,这篇文章的发表被公认为是图论产生的里程碑。自二十世纪五十年代以来,计算机科学的迅猛发展大大地推动了图论的发展。现在,图论已经成为离散数学的一个骨干分支,它不仅具有重要的理论价值,而且具有重要的应用价值。其在化学、信息学、网络设计、管理科学、通信工程、计算机科学以及生物信息学等领域都得到了广泛应用。图的哈密尔顿性、染色理论以及最短路问题作为图论中的经典问题,得到了大量图论专家的关注。本文主要研究谢尔宾斯基相关图类的哈密尔顿性、染色理论以及最短路问题,其中染色理论包括路染色、线性染色以及2-距离染色。谢尔宾斯基相关图类与拓扑分形理论、汉诺塔数学理论及计算机科学等都有密切的联系。下面,首先介绍谢尔宾斯基相关图类S(n,k)、S+(n,k).S++(n,k)和s[n,k]的定义。谢尔宾斯基图S(n,k)(n,k≥1)的顶点集是由整数1,2….,κ的所有的n元组构成的,即V(S(n,k))={1,…,k)n。两个不同的顶点u=(u1,u2,…,un.)和v=(v1,u2,…,vn)相邻当且仅当存在一个h∈[1,n]使得下面三个条件成立:(a)ut=vt,其中t∈{1,…,h-1};(b)uh≠vh;(c)ut=vh和vt=uh,其中t∈{h+1,…,n}。在S(n,k)中,顶点(i,…,i),i∈{1,…,k},称为谢尔宾斯基图S(n,κ)的极点;形如(i,j,…,j)或者(i,…i,j)的顶点称为S(n,κ)的几乎极点。把不属于任何一个完全图的边称为桥边图S+(n,k)(n,k≥1)是在谢尔宾斯基图S(n,κ)的基础上,添加一个新的顶点ω和所有连接ω与S(n,κ)的k个极点的边得到的图。对于图S++(n,k),令S++(1,k)≌Kk+1;图S++(n,k)(n≥2,k≥1)的顶点集合V(S++(n,k))=V(S(n,k))∪V(S(n-1,k)),边的集合E(S++(n,k))=E(S(n,k))∪E(S(n-1,k))∪M,其中,M是一个含有κ条边的匹配,并且M中每条边的两个端点分别是S(n,κ)的一个极点和S(n-1,k)的一个极点。图S[n,k]是通过收缩谢尔宾斯基图S(n,κ)中所有桥边得到的图。给定一个图G,如果G中的一条路遍历了它所有顶点,则称这条路为图G的一条哈密尔顿路。类似的,若图G中的一个圈遍历了它的所有顶点,则称这个圈为图G的一个哈密尔顿圈。若G中存在一个哈密尔顿圈,则称G为哈密尔顿图。图G的一个t-染色就是一个映射φ:V(G)→{1,…,t)。给定图G的一个t-染色φ,我们用φ-1(i)记图G中染色为i的顶点的集合,并把图G中φ-1(j)的导出子图记为G[φ-1(i)]。如果每一个G[φ-1(i)],i∈{1,…,t},是图G的一个独立集,那么称φ为图G的一个正常t-染色。图G的色数x(G)就是使图G存在一个正常t-染色的最小的t。如果每一个G[φ-1(i)],i∈{1,…,t),是图G的一个线性森林,那么称φ为图G的一个路t-染色,其中,线性森林指的是每个连通分支都为路的图。图G的点线性荫度vla(G)就是使图G存在一个路t-染色的最小t。换句话说,图G的点线性荫度vla(G),就是划分它的顶点集所需要的顶点子集的最小个数,同时满足每个顶点子集在G中的导出子图为一个线性森林。如果每一个G[φ-1(i)∪φ-1(j)],i,j∈{1,…,t),是图G的一个线性森林,那么称φ为图G的一个线性t-染色。图G的线性色数lc(G)就是使图G存在一个线性t-染色的最小的t。图G的2-距离染色就是对图G的顶点进行染色使距离至多是2的顶点染不同的颜色。给定一个图G,对于任意两个顶点u,v∈V(G),u与v之间的最短路就是连通它们的长度最小的路。本文讨论了谢尔宾斯基相关图类S(n,k).S+(n,k).S++(n:k)和S[n,k]的哈密尔顿性、染色问题和最短路问题。具体说来,主要研究了谢尔宾斯基相关图类的哈密尔顿性、路染色、线性染色与谢尔宾斯基图S(n,κ)的2-距离染色和最短路问题。本文内容共分为四章。第一章,首先,介绍了一些图论中基本的概念、术语和符号;然后,给出了谢尔宾斯基相关图类的定义及研究现状;最后,列出了本文所得到的主要结果。第二章,分别确定出了S(n,k).S+(n,k)和S++(n,k)中边不交的哈密尔顿路和哈密尔顿圈的个数。第三章,研究了谢尔宾斯基相关图类的路t-染色、线性染色和2-距离染色。第四章,主要讨论了谢尔宾斯基图S(n,κ)中的最短路问题。完全确定出了Su={u∈V(S(n,k)):在S(n,k)中存在两条最短的u,v-路},其中,u是S(n,κ)的任意一个几乎极点。此外,对于S(n,3),我们找到了(n-3)·3n+3·2n对顶点使得每一对顶点之间存在两条不同的最短路并且刻画出了它们的特征,从而给出了S(n,3)中关于两个顶点之间有两条最短路的一个充分条件。
【作者】薛兵;
【导师】李国君;
【作者基本信息】山东大学,运筹学与控制论,2014,博士
【关键词】谢尔宾斯基图;哈密尔顿性;染色;最短路;汉诺塔图;

【参考文献】
[1]邓红军.用户使用视角的政府门户网站效用及影响因素研究[D].浙江大学,2008.
[2]陆犇,韩庆兰.国内超市零售企业客户关系管理的改进[J].莆田学院学报,2002,04:5-8.
[3]熊尚聪.论认知逻辑在刻画实际认知过程中的困境与出路[D].中国政法大学,逻辑学,2014,硕士.
[4]刘开第,刘昕,赵奇,周少玲.基于分类权与质心驱动的无监督学习算法[J].自动化学报,2009,05:526-531.
[5]慕红宇,熊金明.基于数据仓库的数据挖掘技术[J].绍兴文理学院学报(自然科学版),2002,01:45-49.
[6]段敏,许龙飞.生物DNA序列比对算法研究[J].佳木斯大学学报(自然科学版),2005,02:153-158.
[7]奚春蕊.金枪鱼生鱼片品质变化及快速评价方法建立[D].上海海洋大学,食品科学与工程,2013,硕士.
[8]熊颖.不可约马链、细集的性质及应用[D].湖北大学,概率论与数理统计,2012,硕士.
[9]崔镇花.维持性血液透析患者抑郁、焦虑与神经营养因子关系研究[D].延边大学,内科学,2014,博士.
[10]毛万里.79例乳腺癌肺转移的危险因素分析[D].大连医科大学,肿瘤学,2012,硕士.
[11]杨建国.110指挥机制改革的探讨[J].警察技术,2004,02:43-46+25.
[12]常宇春.基于多路径双向拍卖的无线传感器网络路由协议设计[D].苏州大学,计算机技术(专业学位),2013,硕士.
[13]许晔.医药购销领域的商业贿赂行为法律规制研究及治理机制探究[D].上海交通大学,法律,2013,硕士.
[14]周晓芳.当代大学生恋爱心理研究[D].沈阳航空航天大学,思想政治教育,2013,硕士.
[15]年晓红.具有多个执行机构的Lurie控制系统的鲁棒稳定性[J].自动化学报,1998,04:132-135.
[16]田晓燕.企业并购中的人力资源整合[D].东北财经大学,企业管理,2003,硕士.
[17]高晓仙.关联理论视角下《老子》英译本中显化与隐化研究[D].西北师范大学,英语语言文学,2013,硕士.
[18]肖蓓蓓.新型铂基氧气还原反应催化剂结构及催化性能的第一性原理研究[D].吉林大学,2014.
[19]邢强.西北五省经济发展与碳排放量的关系研究[D].兰州商学院,统计学,2014,硕士.
[20]高远.玉米象(Sitophilus zeamais Motschulsky)试验种群生物学特性及生态学特征的研究[D].云南农业大学,农业昆虫与害虫防治,2014,硕士.
[21]赵倩.水性环氧树脂乳液的制备与性能研究[D].湖北大学,高分子化学与物理,2011,硕士.
[22]杨芬群.基于ZigBee技术的低压电器现场参量采集系统的设计与研究[D].温州大学,计算机应用技术,2012,硕士.
[23]赵彩云,常晋义.数据挖掘在外贸业务分析决策中的应用[J].常熟理工学院学报,2005,06:75-79.
[24]朱淑芳.中国电信产业区域竞争力研究[D].浙江工商大学,产业经济学,2013,硕士.
[25]罗珉.组织间关系理论最新研究视角探析[J].外国经济与管理,2007,01:25-32.
[26]田双双.A保险公司服务质量提升研究[D].河北大学,工商管理(专业学位),2014,硕士.
[27]龙关君.我国环境税费整合性研究[D].浙江财经学院,财政学,2012,硕士.
[28]童调生.考虑电枢电感的电力拖动最小能耗控制及奇异解算法的研究[J].自动化学报,1988,03:199-206.
[29]郭丽娜.新疆巴里坤地区下石炭统黑山头组地层划分与对比及沉积特征研究[D].长安大学,古生物学与地层学,2014,硕士.
[30]朴东升.基于非真实感绘制技术的三维可视化方法研究[D].哈尔滨工业大学,计算机科学与技术,2013,硕士.
[31]张辂.翻译可译性研究[D].辽宁师范大学,英语语言文学,2003,硕士.
[32]李天文.高中信息技术自主学习模式的应用研究[D].山东师范大学,教育(专业学位),2013,硕士.
[33]董津佑.金融危机后英国金融监管体制改革分析[D].吉林大学,世界经济,2013,硕士.
[34]雷彪.单相逆变器无连线并联技术研究[D].浙江大学,2006.
[35]郭进,刘侠,董迪,朱守平,杨鑫,田捷.活体光学投影断层成像系统与应用[J].自动化学报,2013,12:2043-2050.
[36]顾彬.苏南农村独生子女父母养老问题研究[D].南京师范大学,社会学,2012,硕士.
[37]周道.航空叶片冷辊轧过程仿真分析[D].东北大学,机械设计及理论,2010,硕士.
[38]邵文北.卫星光通信中光斑图像处理算法优化设计研究[D].哈尔滨工业大学,光学工程,2013,硕士.
[39]张永垒,侯继峰,朱西深,曹源.城轨车辆常用制动隔离系统设计研究[J].中国铁路,2014,05:115-117.
[40]任虎鸣.石墨烯和氧化石墨烯的制备及力学性能研究[D].湘潭大学,2013.
[41]祝文君.构建我国刑事被害人社会救济制度研究[D].贵州民族大学,法律,2013,硕士.
[42]韩春龙.地铁公安安防系统工程项目管理研究[D].吉林大学,工程管理,2012,硕士.
[43]朱相宇,乔小勇.北京环境污染治理分析及政策选择[J].中国软科学,2014,02:111-120.
[44]邓冠南,牛冬杰.微生物燃料电池阴极研究进展[J].能源与节能,2015,03:70-73.
[45]王建文.SUV转向系统振动CAE分析及试验研究[D].华南理工大学,车辆工程,2013,硕士.
[46]赵金一.新千年的挑战:关于中国数字图书馆建设实践的思考[J].图书情报工作,2001,03:20-23.
[47]王永芳.论谢榛的诗歌意象批评[D].湖南师范大学,文艺学,2014,硕士.
[48]刘宇航.活塞二阶运动特性及其影响因素分析研究[D].中北大学,动力机械及工程,2014,硕士.
[49]李东阳.尼可地尔对缺血性心肌病患者心功能影响的临床研究[D].河北医科大学,内科学(专业学位),2014,硕士.
[50]李克雷.水泥生产过程分解炉智能控制系统的设计与开发[D].东北大学,控制理论与控制工程,2010,硕士.

相关推荐
更多