本书系统介绍互连网络拓扑结构设计和分析中的基本组合理论和方法。内容包括网络与图论的基本概念,网络性能的基本度量;网络设计的基本原则和方法(如线图,Cayley和笛卡儿方法);某些著名的网络拓扑结构(如超立方体网络,de Brujin网络,Kautz网络,循环网络等)和它们的基本结构性质以及各种推广;容错网络分析中的基本度量参数(如路由转发指数、容错直径、宽直径、限制直径、距离控制数、限制连通度)的基本理论、研究进展和最新成果。
样章试读
目录
- 目录
第一部分 互连网络和图的基本概念
第1章 互连网络和固的基本概念 3
1.1 图和互连网络 3
1.2 图的基本概念和记号 6
1.3 树,图的嵌入和平面图 12
1.4 网络传输延迟与图的直径,路由选择 16
1.5 网络容错性和图的连通度 23
1.6 网络设计的基本原则 27
习题 29
第二部分 互连网络拓扑结构设计的基本方法
第2章 网络设计的线图方法 33
2.1 线图的概念和基本性质 33
2.2 线图的连通度与直径 36
2.3 线图的Euler 性和Hamilton 性 37
2.4 多重线图 38
2.5 元向线图的边连通度 40
习题 43
第3章 网络设计的Cayley 方法 44
3.1 群的基本知识 44
3.2 可迁图 46
3.3 图的原子 52
3.4 可迁图的连通度和边连通度 54
3.5 Cayley 图 57
3.6 Cayley 图的可迁性 60
3.7 Cayley 图的原子与连通度 63
3.8 素阶点可迁图 65
习题 67
第4章 网络设计的笛卡儿乘积方法 68
4.1 图的笛卡儿乘积 68
4.2 笛卡儿乘积图的直径和连通度 72
4.3 笛卡儿乘积图的其他性质 78
4.4 Cayley 图的笛卡儿乘积 79
习题 82
第5章 优化设计中的一个基本问题 83
5.1 (d,k)无向图问题 83
5.2 (d,k)有向图问题 86
5.3 直径与连通度之间的关系 89
习题 92
第三部分著名的互连网络拓扑结构
第6章 超立方体网络 95
6.1 超立方体网络的定义和基本性质 95
6.2 Gray 码与超立方体中的圈和路长 98
6.3 超立方体网络的子网嵌入问题 102
6.4 超立方体网络的推广 104
6.5 超立方体网络的变形 106
习题 110
第7章 De Brujin 网络 112
7.1 De Brujin 网络的定义和基本性质 112
7.2 De Brujin 网络中最短路的唯一性 116
7.3 广义de Brnjin 网络 120
习题 126
第8章 Kautz 网络 127
8.1 Kautz 网络的定义和基本性质 127
8.2 广义Kautz 网络 130
8.3 广义Kautz 网络的连通度 132
习题 135
第9章 双环网络 136
9.1 双环网络 136
9.2 平面L形瓦 137
9.3 双环网络的直径 141
9.4 双环网络的最优设计 146
9.5 循环网络的基本性质 150
习题 155
第10章 其他网络拓扑结构 157
lO.1 网状网与格网 157
lO.2 金字塔网 158
10.3 立方连通圈网 160
10.4 蝶形网 162
10.5 Benee 网 166
10.6 n网 168
l0.7 移位交换网 169
习题 170
第四部分 互连网络拓扑结构分析171
第11章 互连网络中的路由选择 173
11.1 路由选择的转发指数 173
11.2 路由选择的边转发指数 181
11.3 某些著名网络的转发指数 186
11.4 容错路由选择的传输延迟 190
11.5 幸存路径图直径的某些上界 192
习题 196
第12章 互连罔络的容错直径 198
12.1 交错图的直径 198
12.2 互连网络的边容错直径 203
12.3 容错直径与变更图直径之间的关系209
12.4 互连网络的点容错直径 211
12.5 某些网络的点容错直径 216
习题 220
第四章并行系统中Menger 型问题 221
13.1 点不交限长路问题 221
13.2 Menger 数与有界连通度 227
13.3 边不交限长路问题 231
13.4 点不交超长路问题 234
13.5 网络的Rabin 数 236
习题 239
第14章 互连网络的宽直径 240
14.1 网络的宽直径 240
14.2 正则图的宽直径243
14.3 笛卡儿乘积的宽直径 245
14.4 宽直径与独立数 249
14.5 宽直径与容错直径 252
14.6 某些网络的宽直径 255
习题 258
第15章 (l,w)独立数与(l,w)控制数 259
15.1 (l,w)独立数 259
15.2 (l,w)控制数 262
15.3 距离独立数与距离控制数 265
习题 269
第16章 互连网络的限制容错分析 270
16.1 网络的限制连通度 270
16.2 网络的限制边连通度 272
16.3 可迁图的限制边连通度 279
16.4 网络的超连通性和超连通度 282
16.5 线图的超连通性和超连通度 288
16.6 网络的高阶超连通度 290
16.7 某些网络的限制连通度和超连通度 298
习题 300
参考文献 301
记号索引 318
名词索引 325
《现代数学基础丛书》已出版书目 334