第4章 网络拓扑分析法-1.pdf

网络分析与测试 顾军 计算机学院网络工程系 jgu@cumt.edu.cn 第4章 网络拓扑分析法 第1节图论基础 第2节最短路问题 第3节 网络流问题 第1节图论基础  拓扑结构是网络规划和设计的第一层 次问题。  计算机网络的拓扑结构可以用图论的 模型来描述。 1.1 图与网络优化的例子 例1 最短路问题 (SPP－shortest path problem) 一名货柜车司机奉命在最短的时间内将一车货 物从甲地运往乙地。从甲地到乙地的公路网纵横交 错，因此有多种行车路线，这名司机应选择哪条线 路呢？假设货柜车的运行速度是恒定的，那么这一 问题相当于需要找到一条从甲地到乙地的最短路。 例2 公路连接问题 某一地区有若干个主要城市，现准备修建高速 公路把这些城市连接起来，使得从其中任何一个城 市都可以经高速公路直接或间接到达另一个城市。 假定已经知道了任意两个城市之间修建高速公路的 成本，那么应如何决定在哪些城市间修建高速公路， 使得总成本最小？ 例3 运输问题(transportation problem) 某种原材料有N个产地，现在需要将原材料从 产地运往M个使用这些原材料的工厂。假定N个产 地的产量和M家工厂的需要量已知，单位产品从任 一产地到任一工厂的运费已知，那么如何安排运输 方案可以使总运输成本最低？ 例4 中国邮递员问题 (CPP－Chinese postman problem) 一名邮递员负责投递某个街区的邮件。如何为 他 （她）设计一条最短的投递路线 （从邮局出发， 经过投递区内每条街道至少一次，最后返回邮局）？ 由于这一问题是我国管梅谷教授1960年首先提出的， 所以国际上称之为中国邮递员问题。 例5 旅行商问题 (TSP－traveling salesman problem) 一名推销员准备前往若干城市推销产品。如何为 他 （她）设计一条最短的旅行路线 （从驻地出发，经 过每个城市恰好一次，最后返回驻地）？这一问题的 研究历史十分悠久，通常称之为旅行商问题。 上述问题有两个共同特点： 一是它们的目的都是从若干可能的安排或 方案中寻求某种意义下的最优安排或方案， 数学上把这种问题称为最优化或优化 (optimization)问题； 二是它们都易于用图形的形式直观地描述 和表达，数学上把这种与图相关的结构称 为网络(network)。 图论是数学的一个分支，它以图为研究对象，图 论中的图是若干给定的点及连接两点的线所构成的 图形，这种图形通常用来描述某些事物之间的某种 特定关系。 用点代表事物，用连接两点的线表示相应两个 事物间具有这种关系。因此这种图中点的位置， 线的长短曲直是无关紧要的。 近几十年来，由于计算机技术和科学的飞速发展， 大大地促进了图论研究和应用，图论的理论和方法 已经渗透到物理、化学、通讯科学、建筑学、生物 遗传学、心理学、经济学、社会学等学科中。  与图和网络相关的最优化问题就是网络最优化 或称网络优化(network optimization)问题。上面 例子中介绍的问题都是网络优化问题。  由于多数网络优化问题是以网络上的流(flow) 为研究的对象，因此网络优化又常常被称为网络 流(network flows)或网络流规划等。 1.2 图论的发展 图论起源于18世纪。第一篇图论论文是瑞士数 学家欧拉于1736 年发表的 “哥尼斯堡的七座桥”。 1847年，克希霍夫为了给出电网络方程而引进了 “树”的概念。1857年，凯莱在计数烷的同分异构 物时，也发现了 “树”。 哈密尔顿于1859年提出“周游世界”游戏，用 图论的术语，就是如何找出一个连通图中的生成圈。 哥尼斯堡七桥(Königsberg Bridges)问题 在哥尼斯堡有七座桥 将普莱格尔河中的两个岛 及岛与河岸联结起来问题 是要从这四块陆地中的任 何一块开始通过每一座桥 正好一次，再回到起点。 欧拉(Euler)解决了这个问题！ 将问题用图表示： 四块被分开的区域作为点 连结它们的桥作为边 本质是一笔画问