通信网图论及应用PDF电子书下载

第1章　通信网概述 1

1.1　通信网的基本概念 1

1.1.1　通信的基本概念 1

1.1.2　通信网的构成要素 3

1.1.3　通信网的拓扑结构 3

1.2　通信网的网络体系结构 5

1.2.1 OSI协议的体系结构 5

1.2.2　TCP/IP协议体系结构 7

1.3　通信网路由选择、流量分配与控制 8

1.3.1　路由选择 8

1.3.2 流量分配与控制 11

1.4　通信网的质量要求 12

第2章　通信网图论基础 14

2.1　抽象图和网络的基本概念 14

2.1.1　抽象图的定义 14

2.1.2 图的连通性和可靠通信网的建设问题 19

2.1.3 图的通路、路径和回路 23

2.1.4 图的同构 24

2.1.5 图的操作 25

2.2 图的平面性和对偶性 27

2.2.1 图的可平面性 27

2.2.2　对偶图 30

2.2.3 印刷电路板的设计 31

2.2.4　场地布局规划 35

2.3　图的矩阵表示 35

2.3.1 图的关联矩阵 36

2.3.2 图的回路矩阵 38

2.3.3 图的割矩阵 40

2.3.4　图的邻接矩阵 43

第3章　通信网的路由选择和最短路径 45

3.1　路由和最短路径的概念 46

3.2　确定节点到其他节点最短路径算法 47

3.2.1　Dijkstra算法及修正算法 48

3.2.2　Ford-Moore-Bellman算法 60

3.2.3 叶（Yen）算法 64

3.2.4　Ford-Fulkerson算法 66

3.3　任意节点之间最短路径算法 68

3.3.1　距离矢量路由算法 68

3.3.2　Floyd-Warshall算法 72

3.3.3　链路状态路由算法 76

3.4　通信网络路由选择的其他问题 77

3.4.1 次最短路径和可用路径 78

3.4.2　通信网的中心和中点站址选择 78

3.5　路由算法应用 79

3.5.1　稀疏网络最短路径 79

3.5.2　一种基于并行运算和节点关联优化的快速路由算法 82

第4章　通信网络的最大流 86

4.1 网络流与流量控制基本概念 86

4.1.1 流 86

4.1.2　可行流 87

4.1.3 流量分配与控制 88

4.2　最大流最小割定理 90

4.2.1　s-t割及割容量 90

4.2.2　最大流最小割定理 91

4.3　Ford-Fulkerson最大流算法 93

4.4　基于分层网阻塞流的方法求最大流 96

4.4.1 分层网 96

4.4.2　阻塞流算法 98

4.5　基于冗余网的方法求最大流 100

4.5.1 冗余网 100

4.5.2　最大容量增广路 101

4.5.3　容量可变的增广路 101

4.5.4　最短增广路算法 102

4.6　基于流推进的方法求最大流 104

4.7　特殊网络的最大流 107

4.7.1 无向网和混合网络的最大流 107

4.7.2　基于交换节点容量有限的最大传输能力优化 108

第5章　最小费用流 111

5.1　基本理论 111

5.1.1 最小费用流问题 111

5.1.2　最小费用流数学模型 112

5.2　最小费用最大流和最小费用循环流 114

5.2.1 最小费用流消圈算法 114

5.2.2　最小费用路算法 116

5.2.3 最小费用最大流算法 117

5.2.4　原始—对偶最小流算法 118

5.2.5　最小费用循环流算法 121

5.3　最小费用流应用举例 125

5.3.1　基于最短时延约束的最小费用移动卫星网络优化 125

5.3.2　最小费用最大流算法及编程实现 129

第6章　最小树和最优通信网 132

6.1 基本概念 132

6.1.1　树 132

6.1.2　最小树和最大树 134

6.2　最小树和最大树算法 135

6.2.1 Boruvka算法 136

6.2.2　Kruskal算法 138

6.2.3　Prim算法 139

6.2.4　Sollin算法 141

6.2.5　有根的最小树简易算法 143

6.3　最优通信网举例 145

6.3.1　基于节点数有限的最小树优化通信网拓扑结构 145

6.3.2　基于建站费用最小的遗传算法求最小树 148

6.3.3　基于破圈的最小树构造方法 150

参考文献 155