图中短圈及相关问题

发布时间：2017-12-11 13:25

  本文关键词：图中短圈及相关问题

  更多相关文章： 最短圈 广探树 Euler公式 图染色

【摘要】：短圈是图的重要结构.本文的第二章到第四章主要介绍了找到各类图中短圈的算法.第二章主要介绍了一种找到平面图中任意两点之间的所有最短路的算法,同时证明了平面连通图G中非测地的最短偶长圈一定是某棵支撑树的基本圈或是两个基本圈的和.在找平面连通图G中的最短奇长圈时,得到结论:如果最短奇长圈是图G中的最短圈,那么我们可以找到图中的所有最短奇长圈;否则,可以利用算法找到一个最短奇长圈.第三章我们研究的是特殊情况下的符号图中的最短正圈以及最短负圈.主要利用广探树算法,最终得到了如果符号图中的最短正圈(负圈)的长度大于最短负圈(正圈)的长度,那么最短正圈(负圈)是一个基本圈或是两个基本圈的和,从而得到了符号图中的最短圈是一个基本圈或是两个基本圈的和.第四章研究的是赋权图中的短圈结构.利用Dijkstra算法,我们设计了一种算法可以找到赋权图中的一个最短偶长圈.在本文的第五章,我们主要利用Euler公式以及Gallai提出的研究色临界图的方法,用一种较简单的方法证明了曲面S上7-色临界图的个数是有限的,且计算出了曲面S上的7-色临界图中至多有120(g-1)个点,其中g ≥ 2.同时也给出了曲面S上的每一个k-色临界图(k≥ 7)点数的上界为 12(k + 3)(g-1),其中 k≥7,g≥2.
【学位授予单位】：华东师范大学
【学位级别】：硕士
【学位授予年份】：2017
【分类号】：O157.5

【相似文献】

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

1 王顺年;;分数染色临界图及其性质[J];科学技术与工程;2006年24期

2 刘峙山;关于边着色临界图的一个问题[J];内蒙古师大学报(自然科学汉文版);1991年04期

3 杜之亭，，孙惠泉;若干色临界图和色极小图的构造[J];北京邮电大学学报;1994年04期

4 欧阳克智,张忠辅,张建勋;全着色临界图[J];兰州大学学报;1991年02期

5 苗连英;苗正科;段滋明;曲积彬;;边色临界图的1-因子和几乎1-因子的存在性[J];中国矿业大学学报;2008年01期

6 李雪峰;;一种构造k—色临界图的方法[J];廊坊师范学院学报(自然科学版);2009年03期

7 苗连英;杨星星;苗正科;;边色临界图的1-因子和几乎1-因子的存在性[J];中国矿业大学学报;2010年02期

8 曲积彬;;最大度为9和10时边染色临界图的下界[J];黑龙江科技学院学报;2007年06期

9 龚和林;舒情;;色临界图的最大度与色数的一个关系式[J];数学的实践与认识;2012年07期

10 王发友,王万方,任庆军;路色数临界图[J];临沂师专学报;1999年03期

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

1 齐林明;关于边染色临界图有关性质的研究[D];中国矿业大学;2015年

2 刘兵兵;曲面上嵌入图染色的综述[D];华东师范大学;2015年

3 李青青;图中短圈及相关问题[D];华东师范大学;2017年

4 王顺年;图的分数染色[D];山东师范大学;2007年

5 范青菊;全着色临界图及邻点可区别全着色[D];山西大学;2008年

本文编号：1278626