学位论文 > 优秀研究生学位论文题录展示

2-连通[4，2]-图中的圈与高连通度图的完全圈可扩性

作　者: 刘晓妍
导　师: 王江鲁
学　校: 山东师范大学
专　业: 应用数学
关键词: [ s ,t]-图连通度 s-点连通图完全圈可扩性
分类号: O157.5
类　型: 硕士论文
年　份: 2006年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

图的哈密顿问题是图论中一个十分重要且又十分活跃的研究课题,每年都有大量的关于这一问题的学术论文。1857年,爱尔兰数学家哈密顿提出:“一个连通图有哈密顿圈的充要条件是什么?”这样一个问题。但是这个问题至今仍未能解决。后来人们发现它是一个NPC问题,于是降低要求间接研究该问题。与此同时,以Hamilton问题为出发点发展起了对图的圈性质的研究,这些性质主要包括Hamilton性、泛圈性、完全圈可扩性等。我们知道图的完全圈可扩性要比图的泛圈性更强,图的泛圈性要比图的哈密顿性更强,所以研究泛圈性和完全圈可扩性就研究了图的Hamilton性。关于哈密顿性的研究及最新进展可见参考文献[17]-[23]。关于泛圈性的研究及最新进展可见参考文献[24]-[34],关于完全圈可扩性的研究及最新进展可见参考文献[4]-[15]。对这些性质的研究主要集中在两方面,一方面是寻求这些圈性质的充分条件,另一方面是研究某些特殊图类的圈性质。本文主要讨论了两种特殊图类中的圈性质的问题。一种图类是[ s ,t]-图,刘春房最早提出了[s,t]-图的概念并进行研究的。对[s,t]-图的研究有着深刻的应用价值,很典型的一个应用就是在计算机的网络配置上。另一种图类是高连通度图。这里的高连通度是指一个图的连通度相对图的阶是较高的。当一个图的连通度足够高时,这个图可以保证图的各种圈性质,那么随着图的连通度的降低,图的圈性质将发生什么变化呢?本文就此讨论了高连通度图的完全圈可扩性。为方便讨论,在第三章中提出了s-点连通图的概念,即连通度为κ(G)= |G|-s+1的图。在此基础上主要讨论了5-点连通图,6-点连通图的完全圈可扩性,即连通度分别为|G|-4和|G|-5的高连通度图的完全圈可扩性。根据所得结果提出了s -点连通图

全文目录

中文摘要  5-8
英文摘要  8-12
第一章预备知识  12-16
  1.1 符号概念介绍  12-13
  1.2 研究背景及已有结果  13-16
第二章 2-连通[4,2]-图中的圈  16-22
  2.1 主要结果  16-17
  2.2 定理2.1.1 证明  17-22
第三章高连通度图的完全圈可扩性  22-47
  3.1 引言  22-24
  3.2 主要结果的证明  24-47
参考文献  47-50
攻读学位期间发表的学术论文目录  50-51
致谢  51

2-连通[4，2]-图中的圈与高连通度图的完全圈可扩性

内容摘要

全文目录

相似论文