| 【中文题名】 | 字母重叠图的一些指标 |
| 【英文题名】 | Some Indices of Alphabet Overlap Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2007-8-20 |
| 【中关键词】 | 无向de,Bruijn图,字母重叠图,直径,围长,自同构 |
| 【英关键词】 | Undirected de Bruijn graph,Alphabet overlap graphs,Diameter,Girth,Automorphism,Connectivity,Super edge connectivity, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 |
无向de Bruijn图常被用作通讯网络模型。它具有高效网络应该具有的许多特性，如短直径，小最大度和多结点。我们研究了一类比无向de Bruijn图更广泛的图，字母重叠图G(k，d，s)。它的顶点集V={v|v=(v_1，…，v_k)；v_i∈{1，2，…，d}(1≤i≤k)}，任意两个不同的顶点u=(u_1，…，u_k)，v=(v_1，…，v_k)之间有边当且仅当u_(i+s)=v_i(1≤i≤k-s)或者v_(i+s)=v_i(1≤i≤k-s)。在此定义下，当s=1时，字母重叠图恰是无向de Bruijn图。在本文中，我们得到了字母重叠图G(k，d，s)的以下结果：给出了G(k，d，s)的顶点度表达式，计算出直径和围长分别为[k/s]和3，构造了d~s+1个自同构。当s≥k/2时，证明了G(k，d，s)的连通度为2d~s-2d~(k-2t)，并且是超边连通的。 |
| 【论文题纲】 |
|
摘要 |
4-5 |
|
ABSTRACT(英文摘要) |
5-8 |
|
第一章 引言 |
8-13 |
|
1.1 基本概念和记号 |
8-10 |
|
1.2 本文涉及图的一些相关结论 |
10-12 |
|
1.2.1 连通度 |
10-11 |
|
1.2.2 超边连通性 |
11-12 |
|
1.3 研究结果 |
12-13 |
|
1.3.1 de Bruijn图的结果 |
12 |
|
1.3.2 字母重叠图的结果 |
12-13 |
|
第二章 字母重叠图G(k,d,s)的顶点度,直径和围长 |
13-19 |
|
2.1 引言 |
13-14 |
|
2.2 顶点度 |
14-16 |
|
2.3 图G(k,d,s)的直径和围长 |
16-19 |
|
第三章 图G(k,d,s)(s≥k/2)的连通度 |
19-29 |
|
3.1 图G(k,d,s)(s≥k/2)的子图结构 |
19-23 |
|
3.2 图G(k,d,s)(s≥k/2)的连通度 |
23-29 |
|
第四章 图G(k,d,s)(s≥k/2)的超边连通性及自同构 |
29-31 |
|
4.1 图G(k,d,s)(s≥k/2)的边连通度 |
29 |
|
4.2 图G(k,d,s)(s≥k/2)的超边连通性 |
29 |
|
4.3 图G(k,d,s)的自同构 |
29-31 |
|
参考文献 |
31-32 |
|
致谢 |
32 |
|
| 【DOI】 | LunWen.ID:2.2008.11841 |
