网络模型课件

1

网络模型

2许多研究的对象往往可以用一个图表示，研究的目的归结为图的极值问题。本章继续讨论其他几种图的极值问题的网络模型。运筹学中研究的图具有下列特征：（1）用点表示研究对象，用边（有方向或无方向）表示对象之间某种关系；（2）强调点与点之间的关联关系，不讲究图的比例大小与形状；（3）每条边上都赋有一个权，其图称为赋权图。实际中权可以代表两点之间的距离、费用、利润、时间、容量等不同的含义；（4）建立一个网络模型，求最大值或最小值。下面以实例来说明图在道路交通中的应用。图7-1（a）表示某地区的公路交通网，A、B、C、D、E表示五个城镇，A、B、C、D、E之间的连线表示两城镇间的公路，我们研究的问题就是“两城镇间有无公路相通”这一特定关系，那么就可以用图7-1（b）点的网状图来代替图7-1（a）的公路交通图57.1最小树问题7.1.1树的概念

一个无圈并且连通的无向图称为树图或简称树（Tree）如图7-3是一个管道铺设方案路线图，其特征是任意两点之间都有惟一的一条链（路）连通起来，是一棵树。树具有以下性质：在树中任意两点之间添加一条边就形成圈。在树中去掉任意一条边图就变成不连通。一棵树的边数等于点数减1。树中任意两点之间都有惟一的一条链连通起来。77.1.2最小部分树将网络图边上的权看做两点间的长度（距离、费用、时间），定义G的部分树T的长度等于T中每条边的长度之和，记为C（T）。G的所有部分树中长度最小的部分树称为最小部分树，或简称为最小树。如果一个连通图G本身不是一棵树，那么G的部分树不惟一。最小树问题就是在所有部分树中寻找树长最短的部分树。最小部分树可以直接用作图的方法求解，常用的有破圈法和加边法。破圈法任取一圈，去掉圈中最长边，直到无圈。加边法从最短边开始往支撑图中添加，见圈回避，直到连通。7.1.2最小部分树在一个连通图

中，取部分边连接

的所有点组成的树称为

的部分树或支撑数（SpanningTree）。最小部分树可以直接用作图的方法求解，常用的有避圈法和破圈法。破圈法：取图

中任一一个圈，从圈中去掉一条权最大的边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条）。在余下的图中，重复这个步骤，直到得到一个不含圈的图为止，这时的图便是最小树。7.2最短路问题所谓最短路问题,就是在一个网络中,相邻节点间的线路长度是已知的,要从某一起点到某一终点之间,找出一条路长最短的通路。7.2.1有向图的Dijkstra算法137.2最短路问题7.2.1有向图的Dijkstra算法14到此，所有节点均标上了标号，算法停止。可见，从城市1到城市7的最小运费为29个单位。用Dijkstra算法求解最短路问题要注意一下问题：Dijkstra算法的条件是弧长非负，问题求最小值。Dijkstra算法求得的最短路线可能不惟一，但最短路长相等。Dijkstra算法可以求任意两点之间的最短路（最短路存在），只要将两个点看做路线的起点和终点，然后进行标号。187.2.2无向图的Dijkstra算法如果vi与vj之间存在一条无方向的边相关联，说明vi与vj两点之间可以互达。当与之间至少有两条边相关联时，留下一条最短边，去掉其他关联边。对于无向图最短路的求解Dijkstra算法同样有效。【例7.4】要在八个城市间建立如图7-9所示的公路交通网。已知城市与城市见的路可以互达，网络边上的数据表示城市间公路的距离，用Dijkstra算法求解城市1到其它城市间公路的最小距离。23456784526139382616121871解

217.2.4最短路的Floyd算法【例7.5】图7-11是一张8个城市的铁路交通图，铁路部门要制作一张两两城市间的距离表。这个问题实际就是求任意两点间的最短路问题。表7-3就是最优表，即任意两点间的最短距离。取表中下三角得到8个城市间的铁路交通距离表。【例7.6】求图7-12中任意两点间的最短距离。解

图7-12是一个混合图，有3条边的权是负数，有两条边无方向。依据图7-12，写出任意两点间一步到达距离表

。表中第一列的点表示弧的起点，第一行的点表示弧的终点，无方向的边表明可以互达，如表7-4所示。计算过程见表7-5至表7-7。307.3最大流问题7.3.1基本概念7.3最大流问题7.3.1基本概念可行流与最大流可行流应满足以下条件：综上，网络最大流问题就是在满足上述条件的基础上寻找一个流

，使其流量达到最大。7.3最大流问题7.3.1基本概念增广链7.3最大流问题7.3.1基本概念割集与割量7.3.2Ford-Fulkerson标号算法【定理7.1】可行流

是最大流的充分必要条件是不存在发点到收点的增广链。Ford-Fulkerson标号算法的步骤如下：

解

（1）给出一个初始可行流，弧的流量放在括号内，如图7-16所示。（2）标号寻找增广链。（3）调整增广链上的流量（4）对图7-18标号。对图7-18的流量进行调整，增广链上弧的流量加上1，其余弧的流量不变得到图7-20。（5）对图7-20标号对图7-20的流量进行调整，增广链上弧的流量加上1，其余弧的流量不变得到图7-22。（6）对图7-22标号。7.3.3最小费用流问题解答过程见图7-25,7-267.4旅行售货员与中国邮路问题7.4.1旅行售货员问题旅行售货员问题虽然能用整数规划、动态规划等方法求解，当

较大时求解就不一定有效。一种可行的方法是求最小的Hamilton回路。下面介绍一下Hamilton回路。7.4.2中国邮路问题给定一个连通多重图

，若存在一条链过每边一次且仅一次，则称这条链为欧拉链。若存在一个简单圈过每边一次且仅一次，称这个圈为欧拉圈。一个图若有欧拉圈，则称为欧拉图。【定理7.2】连通多重图

有欧拉圈，当且仅当

中无奇点。中国邮路问题变为在一个具有奇点的图中，如何将奇点连起来变为偶点成为欧拉图，使各边长之和最短。解

（1）虚拟边将所有奇点变为偶点，如图7-28（b）所示。虚拟边就是邮递员重复经过的街道。7.5网络模型在道路交通工程中的应用【例7.13】服务网点设置以图7-11为例，现提出这样一个问题，在交通网络中建立一个快速反应中心，应选择哪一个城市