| 【中文题名】 | de Bruijn图的限制边连通度 |
| 【英文题名】 | Restricted Edge Connectivity of de Bruijn Digraphs and Graphs |
| 【学科专业】 | 运筹学与控制论 |
| 【论文级别】 | 硕士论文 |
| 【投稿时间】 | 2006-8-24 |
| 【中关键词】 | 网络,限制边连通度,超级限制边连通性,有向de,Bruijn图,无向de |
| 【英关键词】 | networks,restricted edge connectivity,super restricted edge connectivity,de Bruijn digraphs,de Bruijn undirected graphs, |
| 【分类导航】 | 数理科学和化学>数学>代数、数论、组合理论>组合数学（组合学）>图论> |
| 【论文摘要】 | 多处理机系统的互连网络拓扑通常以(无向或有向)图为数学模型,这时图的顶点代表处理机,而一对处理机之间的直接通信联系则用连接这对顶点的边来表示,因此网络拓扑的性能可以通过图的性质和参数来度量。对互连网络性能的一个关键要求是希望网络的可靠(容错)性好,这对应于图论的术语来说,就是希望图的连通度和边连通度大。不过用连通度和边连通度这两个参数考究系统的可靠性有缺陷,因而作为传统边连通概念的推广,Esfahanian和Hakimi提出了限制边连通的概念:设G是无向简单连通图,F是G的一个边割,如果G-F不含孤立点,则称F是G的一个限制边割。最小限制边割所含的边数称为G的限制边连通度(有向图的限制边连通度可类似给出)。限制边连通度是计算机互连网络可靠性的一个重要度量。超级限制边连通性是比限制边连通度更精确的一个网络可靠性指标。一个图是超级限制边连通的,如果它的任一最小限制边割都孤立一条有最小边度的边。本文主要研究了有向de Bruijn图的限制边连通度和无向de Bruijn图的超级限制边连通性。
在第一章我们给出本文将用到的图论方面的主要的术语、记号。并介绍了de Bruijn图和限制边连通度方面的基本... |
| 【论文题纲】 |
|
引言 |
7-8 |
|
第一章 预备知识 |
8-12 |
|
1.1 图论的一些基本术语和记号 |
8-9 |
|
1.2 de Bruijn图的基本概念和基本结论 |
9-10 |
|
1.3 有关连通性的基本概念和基本结论 |
10-12 |
|
第二章 有向de Bruijn图的限制边连通度 |
12-18 |
|
2.1 准备工作 |
12-15 |
|
2.2 主要结论 |
15-18 |
|
第三章 无向de Bruijn图的超级限制边连通性 |
18-26 |
|
3.1 相关结论 |
18 |
|
3.2 准备工作 |
18-22 |
|
3.3 主要结论 |
22-26 |
|
结论 |
26-27 |
|
参考文献 |
27-29 |
|
致谢 |
29-30 |
|
附录 |
30-31 |
|
个人情况 |
31-32 |
|
| 【DOI】 | LunWen.ID:2.2008.11656 |
