通信网图论及应用

第1章通信网概述

1.1通信网的基本概念

1.1.1通信的基本概念

1.1.2通信网的构成要素

1.1.3通信网的拓扑结构

1.2通信网的网络体系结构

1.2.1OSI协议的体系结构

1.2.2TCP/IP协议体系结构

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

1.3.1路由选择

1.3.2流量分配与控制

1.4通信网的质量要求

第2章通信网图论基础

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

2.1.1抽象图的定义

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

2.1.3图的通路、路径和回路

2.1.4图的同构

2.1.5图的操作

2.2图的平面性和对偶性

2.2.1图的可平面性

2.2.2对偶图

2.2.3印刷电路板的设计

2.2.4场地布局规划

2.3图的矩阵表示

2.3.1图的关联矩阵

2.3.2图的回路矩阵

2.3.3图的割矩阵

2.3.4图的邻接矩阵

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

3.1路由和最短路径的概念

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

3.2.1Dijkstra算法及修正算法

3.2.2Ford-Moore-Bellman算法

3.2.3叶(Yen)算法

3.2.4Ford-Fulkerson算法

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

3.3.1距离矢量路由算法

3.3.2Floyd-Warshall算法

3.3.3链路状态路由算法

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

3.4.1次最短路径和可用路径

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

3.5路由算法应用

3.5.1稀疏网络最短路径

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

第4章通信网络的最大流

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

4.1.1流

4.1.2可行流

4.1.3流量分配与控制

4.2最大流最小割定理

4.2.1s-t割及割容量

4.2.2最大流最小割定理

4.3Ford-Fulkerson最大流算法

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

4.4.1分层网

4.4.2阻塞流算法

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

4.5.1冗余网

4.5.2最大容量增广路

4.5.3容量可变的增广路

4.5.4最短增广路算法

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

4.7特殊网络的最大流

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

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

第5章最小费用流

5.1基本理论

5.1.1最小费用流问题

5.1.2最小费用流数学模型

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

5.2.1最小费用流消圈算法

5.2.2最小费用路算法

5.2.3最小费用最大流算法

5.2.4原始-对偶最小流算法

5.2.5最小费用循环流算法

5.3最小费用流应用举例

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

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

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

6.1基本概念

6.1.1树

6.1.2最小树和最大树

6.2最小树和最大树算法

6.2.1Boruvka算法

6.2.2Kruskal算法

6.2.3Prim算法

6.2.4Sollin算法

6.2.5有根的最小树简易算法

6.3最优通信网举例

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

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

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

参考文献

　　本书采用比较通俗的语言和科学的系统结构，主要阐述了以图论建模的方法来优化网络的路由选择和流量控制方法。全书重视基础，强调应用，适应科学研究工作和工程应用要求。可作为高等学校通信工程、计算机网络、电子信息类专业高年级学生的教材和信息类专业硕士研究生的选修课教材，也可以作为通信网基础理论研究、通信网络规划和优化设计、计算机网络等相关领域技术人员和管理人员的参考书。　　本书主要以图论的方法研究通信网的路由选择规划和流量分配优化。从现代通信网络的基础知识入手，分6章对现代通信网的网络基础知识、通信网络的图论模型和矩阵描述方法、通信网的路由选择和最短路径、通信网的最大流分配、最小费用流、最小树和最优通信网构造等基本概念、基本技术和基本方法进行了介绍；对通信网络路由选择、网络规划和优化资源方法及应用作了深入浅出的阐述和分析。　　本书可作为高等学校通信工程、计算机网络、电子信息类专业高年级学生的教材和信息类专业硕士研究生的选修课教材，也可以作为通信网基础理论研究、通信网络规划和优化设计、计算机网络等相关领域技术人员和管理人员的参考书。