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

图的k次方图的宽直径

作　者: 杨超
导　师: 孟吉翔
学　校: 新疆大学
专　业: 运筹学与控制论
关键词: 网络路圈 k-距离直径连通度宽直径 k次方图 Harary图
分类号: O157.5
类　型: 硕士论文
年　份: 2007年
下　载: 17次
引　用: 0次
阅　读: 论文下载

内容摘要

本文共四章，主要研究了三方面的内容：路和树的k次方图的宽直径，并得到图的k次方图的宽直径的界；圈的k次方图的宽直径及给出了含圈图的k次方图的宽直径的界；Harary图的宽直径。行文结构安排如下：第一章介绍文章的研究背景，概念以及主要结论。设G=G（V，E）是简单无向k连通图，u，v是V（G）中任意两个不同的顶点。P_i（1≤i≤k）表示连结u，v的k条内部不交的路。|P_i|表示路P_i的长。记D_k（u，v）所有k条内部不交的（u，v）路。设P_k（u，v）是u和v间的k条内部不交路的集合，即P_k（u，v）={P₁，P₂，…，P_k}，|P₁|≤|P₂|≤…≤|P_k|定义u和v间的k宽距离d_k（u，v）：d_k（u，v）=min{|P_k|：P_k（u，v）∈D_k（u，v）}并且，G的k宽直径定义为：d_k（G）=max{d_x（u，v）：u，v∈V（G），u≠v}。显然，d_k（G）≥d_k-1（G）≥…≥d₁（G）=d（G），其中，d（G）表示G的直径。第二章主要讨论路和树的k次方图的连通度k（G），及由图的连通度与直径相结合所决定的路和树宽直径，即对k≤n-1，d_k（P_n^k）=「n/k」。并且对k≤d（T）-1，d_k（T^k）≤「n/k」。进而我们得到了一般图的k次方图的宽直径：对k≤d（G）-1，d_k（G^k）≤「n/k」。第三章先给出圈的k次方图的连通度k（C_n^k）[21]，主要讨论圈的k次方图的宽直径，即对k≤（n-1）/2，d_2k（C_n^k）=「（n-2）/k」+1。进而，得到含哈密尔顿圈图的k次方图的宽直径的界：对k≤d（G）-1，d_2k（G^k）≤「（n-2）/k」+1。第四章我们由含哈密尔顿圈的k次方图的宽直径，我们联系到Harary图G的宽直径，得到如下结果：对Harary图H_k，n若k和n分别是奇数和偶数，则d_k(H_k，n=「（n-2）/（k-1）」+1 k≤n/2并且，对k＞n/2 d_k(H_k，n≤4。对Harary图H_k，n若k和n均为奇数，那么，d_k(H_k，n-1)≤d_k(H_k，n)≤d_k(H_k，n+1)。

全文目录

Chinese abstract  3-5
English abstract  5-7
Chapter 1. Introduction  7-11
  1.1 Background  7-9
  1.2 Outline  9-11
Chapter 2. Wide diameter of the kth power of paths and trees  11-14
  2.1 Connectivity of the kth power of paths and trees  11-13
  2.2 Wide diameter of the kth power of paths and trees  13-14
Chapter 3. Wide diameter of the kth power of cycles  14-17
  3.1 Some preliminaries and main results  14-15
  3.2 Proofs of the main results  15-17
Chapter 4. Wide diameter of Harary graphs  17-22
  4.1 Some preliminaries  17-18
  4.2 Proofs of the Theorems  18-22
References  22-26
Contents of finished papers  26-27
Acknowledgements  27-28

图的k次方图的宽直径

内容摘要

全文目录

相似论文