运筹学基础及应用第五版-胡运权.ppt

第6章图与网络分析;图是一种模型，如公路铁路交通图，水或煤气管网图，通讯联络图等。;一、根本概念;;4、点v的次〔或度，degree〕

与点v关联的边的条数，记为dG(v)或d(v)。;5、链：图中保持关联关系的点和边的交替序列，其中点可重复，但边不能重复。;v1;7、图G1=｛V1,E1｝,G2={V2,E2},

假设有V1?V2，E1?E2，那么称G1是G2的一个子图；

假设V1=V2，E1?E2且E1≠E2，那么称G1是G2的一个局部图。;二、应用;解：构造一个六阶图如下：;§6.2树图和图的最小局部树;2、树的性质;〔2〕n阶树必有n-1条边。;〔3〕任何有n个点、n-1条边的连通图是树。;3、图的最小局部树;〔2〕最小局部树〔或最小支撑树〕;二、最小局部树的求法;;2、求法;避圈法另一种做法：;例：分别用两种避圈法构造以下图的最小局部树。;3.V={S,A};第二种做法求解过程：;方法二：破圈法求解步骤：;2.从剩余的子图中任找一回路，同样去掉回路中边权最大的一条边，得一新的子图；依次类推。;破圈法的另一种解法：;注意：;§6.3最短路问题;即在的网络图中，从给定点s出发，要到达目的地t。问：选择怎样的行走路线，可使总行程最短？;;〔4〕步骤

在网络图中求s到t的最短路。;;;例求图中任意两点之间的最短距离。;4、矩阵算法

求任意两点间最短距离的方法;其中dij〔1〕=min{dir〔0〕+drj〔0〕};其中dij〔2〕=min{dir〔1〕+drj〔1〕};其中dij〔3〕=min{dir〔2〕+drj〔2〕};说明：

一般的对于D〔k〕=?dij〔k〕?，

其中dij〔k〕=min?{dir〔k-1〕+drj〔k-1〕}，(k=0,1,2,3,…)最多可经过2k-1个中间点;注意;例：以下图中v1—v7表示7个村子，需要联合建立一所小学，各村小学生的人数分别为v1—30人，v2—40人，v3—25人，v4—20人，v5—50人，v6—60人，v7—60人。问：学校应建在哪一个村子，可使学生总行程最少？;;小学建在下列村子时，七个村子的学生上学时单程所走的路程;v1;一、根本概念和根本结论;4、容量网络〔简称网络〕：每条弧都有容量的网络。;6、流〔flow〕：加在网络中弧(vi,vj)上的一组负载量，用f(vi,vj)或fij表示。;10、网络的最大流：即使V(f)到达最大的可行流。;12、割的容量：割集中各弧的容量之和。;14、前向弧〔或正向弧〕：在从发点s到收点t的一条链中，指向为s到t的弧称为前向弧，记做μ+。;二、网络最大流的求法

标号算法(Ford-Fulkerson标号算法);3、步骤：;③当t得到标号时，从t开始沿已标号点用反向追踪法得到增广链，利用ε(t)调整流量：

对前向弧μ+，新流量f?ij=fij+ε(t)

对后向弧μ-，新流量f?ij=fij-ε(t)

其余弧上的流量不变。;8(8);8(8);;;;;§6.5中国邮路问题;奇点：图中次为奇数的点称为奇点。

偶点：图中次为偶数的点称为偶点。;步骤：;v1;§6.6网络模型的实际应用;解：;;;例3：有3根相同的轴A1、A2、A3，另有三根相同的齿轮B1、B2、B3。因为精度不高，不能做到任意的互相配合，其中A1能与B1、B2配合，A2能与B2、B3配合，A3能与B1、B3配合。要求确定适宜的配合方案，以得到最多的配合数，将此问题归为网络最大流问题。