大学精品课件：运筹学（七）.ppt

1、第八章第八章图与网络分析图与网络分析ABCD哥尼斯堡哥尼斯堡“七桥七桥”难难题题1736年，数学家欧拉把该问题归结为下图：年，数学家欧拉把该问题归结为下图：ABCD主要内容：主要内容：第一节第一节 图与网络的基本知识图与网络的基本知识第二节第二节 树树第三节第三节 最短路问题最短路问题第四节第四节 最大流问题最大流问题第五节第五节 最小费用流问题最小费用流问题第一节第一节图与网络的基本知识图与网络的基本知识一、图与网络的基本概念一、图与网络的基本概念 1.1.图及其分类图及其分类图：图：是由点集是由点集V=vV=vi i 和和V V中元素的无序对的一个集合中元素的无序对的一个集合E=eE=ek

2、 k 所构成的二元组，记为：所构成的二元组，记为：G=G=（V,EV,E）。）。V V中的元素中的元素v vi i叫做叫做顶点顶点，E E中的元素中的元素e ek k叫做叫做边边。有限图有限图无限图无限图无向图无向图有向图有向图简单图：不含简单图：不含环环或或多重边多重边的图的图多重图多重图m m（G G）=|E|=|E|称为称为G G中的中的边数，边数，简记为简记为m m；n n（G G）=|V|=|V|称为称为G G中的中的顶点个数，顶点个数，简记为简记为n n。完全图：完全图：每一对顶点都有边相连的无向简单图称为完全图。每一对顶点都有边相连的无向简单图称为完全图。有有n n个顶点的无向完

3、全图记为个顶点的无向完全图记为KnKn。有向完全图：有向完全图：每一对顶点间有且仅有一条有向边的简单图。每一对顶点间有且仅有一条有向边的简单图。二部图：二部图：图图G G（V,EV,E）的点集）的点集V V可以分为两个非空子集可以分为两个非空子集X,YX,Y，即，即X XY=VY=V，X XY=Y=，使得使得E E中每条边的两个端点中每条边的两个端点必有一个属于必有一个属于X X，另外一个属于，另外一个属于Y Y，则称，则称G G为二部图。为二部图。2.2.顶点的次顶点的次顶点的次：顶点的次：以点以点v v为端点的边数叫做点为端点的边数叫做点v v的次，简记为的次，简记为d(vd(v)。悬挂点

4、悬挂点孤立点孤立点奇点奇点偶点偶点定理定理1 1：任何图中，顶点次数的总和等于边数的任何图中，顶点次数的总和等于边数的2 2倍。倍。定理定理2 2：任何图中，次为奇数的顶点必为偶数个。任何图中，次为奇数的顶点必为偶数个。出次：出次：有向图中，以点有向图中，以点v vi i为始点的边数叫做点为始点的边数叫做点v vi i的出次，简的出次，简记为记为d d+(v(vi i)。入次：入次：有向图中，以点有向图中，以点v vi i为终点的边数叫做点为终点的边数叫做点v vi i的入次，简的入次，简记为记为d d-(v(vi i)。v vi i点的出次和入次之和就是该点的次。点的出次和入次之和就是该点的

5、次。有向图中，所有顶点的入次之和等于所有顶点的初次之和。有向图中，所有顶点的入次之和等于所有顶点的初次之和。3.3.子图子图4.4.网络网络子图：子图：图图G=G=（V,E)V,E)，若，若E E是是E E的子集，的子集，V V是是V V的子集，且的子集，且E E中中的边仅与的边仅与V V中的顶点相关联，则称中的顶点相关联，则称G G=(V(V,E,E)是是G G的一个子图。的一个子图。生成子图（支撑子图）：生成子图（支撑子图）：若若G G=(V(V,E,E)是是G G的一个子图，且的一个子图，且有有V V=V=V，则，则G G是是G G的一个生成子图。的一个生成子图。点或边带有某种数量指标的

6、图称为点或边带有某种数量指标的图称为网络（赋权图）网络（赋权图）。二、连通图二、连通图链：如链：如v1,e1,v2,e6,v4,e7,v3,e3,v2,e5,v5v1,e1,v2,e6,v4,e7,v3,e3,v2,e5,v5；初等链：初等链：圈：圈：初等圈：初等圈：v v1 1v v2 2v v3 3v v4 4v v5 5v v6 6e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7e e8 8e e9 9e e1010如如v1,e1,v2,e6,v4,e10,v6,e9,v5v1,e1,v2,e6,v4,e10,v6,e9,v5；如如v1,e1,v2,e

7、5,v5,e8,v4,e6,v2,e3,v3v1,e1,v2,e5,v5,e8,v4,e6,v2,e3,v3，e2e2，v1v1；如如v1,e1,v2,e6,v4,e7,v3v1,e1,v2,e6,v4,e7,v3，e2e2，v1.v1.道路：道路：有向图中，链上的边方向相同时，称为道路。有向图中，链上的边方向相同时，称为道路。回路：回路：有向图中，圈上的边方向相同时，称为回路。有向图中，圈上的边方向相同时，称为回路。连通图：连通图：一个图中任意两点间至少有一条链相连，则称此图一个图中任意两点间至少有一条链相连，则称此图为连通图。为连通图。如：如：v1,e2,v3,e7,v4,e8,v5v1,

8、e2,v3,e7,v4,e8,v5是一条道路；是一条道路；v1,e1,v2,e5,v5,e8,v4v1,e1,v2,e5,v5,e8,v4是一条链但不是一条道路。是一条链但不是一条道路。v v1 1v v2 2v v3 3v v4 4v v5 5e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7e e8 8如：如：v1,e2,v3,e4,v2,e1,v1v1,e2,v3,e4,v2,e1,v1是一条回路；是一条回路；v1,e1,v2,e6,v4,e7,v3v1,e1,v2,e6,v4,e7,v3，e2e2，v1v1是圈但不是一条回路。是圈但不是一条回路。每一个

9、连通图都可以分为若干个连通子图。每一个连通图都可以分为若干个连通子图。三、图的矩阵表示三、图的矩阵表示有权矩阵：有权矩阵：网络（赋权图）网络（赋权图）G=G=（V,EV,E），），|V|=n|V|=n，其边，其边(v(vi i,v,vj j)有权有权w wijij，构造矩阵，构造矩阵A=A=（a aijij）n nn n，其中：，其中：其他其他 0),(Evvwajiijij称矩阵称矩阵A A为网络为网络G G的有权矩阵。的有权矩阵。v v1 1v v2 2v v3 3v v4 4v v5 57 76 64 42 29 95 54 43 38 8 06507608445803204309742

10、90A邻接矩阵：邻接矩阵：图图G=G=（V,EV,E），），|V|=n|V|=n，构造矩阵，构造矩阵A=A=（a aijij）n nn n，其中：其中：其他其他 0),(1Evvajiij称矩阵称矩阵A A为图为图G G的邻接矩阵。的邻接矩阵。0000010000010101110000110Av v1 1v v2 2v v3 3v v4 4v v5 5四、欧拉回路与中国邮路问题四、欧拉回路与中国邮路问题1.1.欧拉回路与道路欧拉回路与道路欧拉道路：欧拉道路：连通图连通图G G中，若存在一条道路，经过每边一次且中，若存在一条道路，经过每边一次且仅一次，则称该道路为欧拉道路。仅一次，则称该道路为

11、欧拉道路。欧拉回路：欧拉回路：连通图连通图G G中，若存在一条回路，经过每边一次且中，若存在一条回路，经过每边一次且仅一次，则称该回路为欧拉回路。仅一次，则称该回路为欧拉回路。欧拉图：欧拉图：具有欧拉回路的图称为欧拉图。具有欧拉回路的图称为欧拉图。定理定理3 3：无向连通图无向连通图G G是欧拉图，当且仅当是欧拉图，当且仅当G G中无奇点。中无奇点。推论推论1 1：无向连通图无向连通图G G是欧拉图，当且仅当是欧拉图，当且仅当G G的边集可划分为的边集可划分为若干个初等回路。若干个初等回路。推论推论2 2：无向连通图无向连通图G G有欧拉道路，当且仅当有欧拉道路，当且仅当G G中恰有两个奇点。

12、中恰有两个奇点。定理定理4 4：连通有向图连通有向图G G是欧拉图，当且仅当它的每个顶点的出是欧拉图，当且仅当它的每个顶点的出次等于入次。次等于入次。2.2.中国邮路问题中国邮路问题 一个邮递员，负责某一地区的信件投递。他每天从邮局一个邮递员，负责某一地区的信件投递。他每天从邮局出发，走遍该地区所有街道再返回邮局，如何安排送信的路出发，走遍该地区所有街道再返回邮局，如何安排送信的路线可以使所走的总路程最短？线可以使所走的总路程最短？G G图中若无奇点，图中若无奇点，则则G G是一个欧拉图，按欧拉回路走即可是一个欧拉图，按欧拉回路走即可。G G图中若有奇点，图中若有奇点，必然有某些边不止走一次，

13、相当于给必然有某些边不止走一次，相当于给G G图中图中某些边增加一些重复边，使得到的新图某些边增加一些重复边，使得到的新图GG无奇点且满足总无奇点且满足总路程最短路程最短。分析分析：此问题可归结为：给定一个连通图：此问题可归结为：给定一个连通图G G，每边有非负权，每边有非负权数数 ，要求一条回路过每边至少一次，且满足总权最小。，要求一条回路过每边至少一次，且满足总权最小。)(el又可以转化为如下问题：又可以转化为如下问题：在连通图在连通图G(V,E)G(V,E)中，求一个边集中，求一个边集 ,把把G G中属于中属于E1E1的边均变为二重边，得到的新图的边均变为二重边，得到的新图G=G+E1G

14、=G+E1，且，且，最小最小。E1E 1Ee(e)1E(Ll要满足该条件，则有：对要满足该条件，则有：对G中的初等圈来讲，中的初等圈来讲，重复边的长度和不超过圈长的一半。重复边的长度和不超过圈长的一半。第二节第二节树树一、树的概念和性质一、树的概念和性质连通且不含圈的无向图称为连通且不含圈的无向图称为树。树。树中次为树中次为1的点称为的点称为树叶树叶树中次大于树中次大于1的点称为的点称为分枝点分枝点1、概念、概念图图T=（V,E），），|V|=n，|E|=m，则下列，则下列关于树的说法是等价的：关于树的说法是等价的：（1）T是一个树；是一个树；2、关于树的性质的定理、关于树的性质的定理（2）T

15、无圈，且无圈，且m=n-1；（3）T连通，且连通，且m=n-1；（4）T无圈，但每加一新边即得唯一一个圈；无圈，但每加一新边即得唯一一个圈；（5）T连通，但任舍去一个边就不连通；连通，但任舍去一个边就不连通；（6）T中任意两点之间，有惟一链相连。中任意两点之间，有惟一链相连。二、图的生成树二、图的生成树若图若图G的生成子图是一棵树，则称该树为的生成子图是一棵树，则称该树为G的生的生成树（支撑树）。简称为图成树（支撑树）。简称为图G的树。的树。1、定义、定义v6v5v2v3v4v1v6v5v3v4v1v2图图G=（V，E）有生成树的充分必要条件是）有生成树的充分必要条件是G为为连通图。连通图。定

16、理：定理：2、寻找支撑树的方法、寻找支撑树的方法（1）破圈法）破圈法（2）避圈法（加边法）避圈法（加边法）深探法深探法广探法广探法v6v5v2v3v4v1v5v6v2v3v4v1v5v6v2v3v4v1v5v6v2v3v4v1破破 圈圈 法法 示示 例例(1)(2)(3)(4)v5v6v2v3v4v1破破 圈圈 法法 示示 例例(5)避圈法示例见课本避圈法示例见课本P255.三、图的最小生成树三、图的最小生成树连通图连通图G=（V，E），每条边上有非负权），每条边上有非负权L（e）。）。一棵生成树所有树枝上的权的总和，称为这个生成一棵生成树所有树枝上的权的总和，称为这个生成树的权。具有最小权的

17、生成树称为最小生成树（最树的权。具有最小权的生成树称为最小生成树（最小支撑数），简称最小树。小支撑数），简称最小树。1、定义、定义2、寻找最小生成树的方法、寻找最小生成树的方法（1）Kruskal法（避圈法）法（避圈法）每步从未选的边中选取边每步从未选的边中选取边e，使它与已选的边，使它与已选的边不构成圈，且不构成圈，且e是未选边中的最小权边，直到选够是未选边中的最小权边，直到选够n-1条边为止。条边为止。（2）破圈法）破圈法 在图中任取一圈，去掉最大权边，重复此操在图中任取一圈，去掉最大权边，重复此操作，直到无圈。作，直到无圈。V1V2V3V4V5V68543678321V1V2V3V4V5

18、V643621Kruskal法法 示示 例例V1V2V3V4V5V68543678121V1V2V3V4V5V68543678321破破 圈圈 法法 示示 例例第三节第三节最最 短短 路路 问问 题题一、最短路问题一、最短路问题 最短路径问题是图论中十分重要的最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。路安排，工厂布局，设备更新等等。最短路径问题的一般提法如下：最短路径问题的

19、一般提法如下：设设G=G=（V V，E E）为连通图，图中各边都有权，）为连通图，图中各边都有权，v vs s,v,vt t为图中两个顶点，求一条道路，使它是为图中两个顶点，求一条道路，使它是从从v vs s到到v vt t所有道路中总权最小的道路。所有道路中总权最小的道路。最短路径问题的求解方法：最短路径问题的求解方法：Dijkstra算法算法求解图中指定点求解图中指定点vs到其到其它任意点的最短路，图中所有边的权为非负数。它任意点的最短路，图中所有边的权为非负数。逐次逼近算法逐次逼近算法求解图中指定点求解图中指定点vs到其它到其它任意点的最短距离，图中的边可以为负数。任意点的最短距离，图中

20、的边可以为负数。Floyd算法算法求解图中任意两点之间的求解图中任意两点之间的最短距离。最短距离。二、二、Dijkstra算法算法步骤：步骤：（1）给初始点）给初始点vs以以P标号，标号，P(vs)=0，其余点为，其余点为T标号，标号，T（vi）=+。（2）若）若vi为刚得到为刚得到P标号的点，考虑这样的点标号的点，考虑这样的点vj:(vi,vj)属于属于E，且，且vj为为T标号。对标号。对vj的的T标号进行如标号进行如下修改：下修改：T(vj)=minT(vj)，P(vi)+lij（3）比较所有具有）比较所有具有T标号的点，把最小者该为标号的点，把最小者该为P标号。标号。返回步骤（返回步骤（

21、2），直到），直到vt为为P标号为止。标号为止。求指定点求指定点vs到其他任意点到其他任意点vt的最短路。的最短路。V1V2V3V4V5V6V76101232557691481116（1）给给v1以以P标号，标号，P（v1）=0，给其余点以给其余点以T标号，标号，T（vi）=+（i=2，7）（2）考察点考察点v1，由于（，由于（v1，v2），（），（v1，v3），（），（v1，v4）属于属于E，且，且v2，v3，v4为为T标号，因此修改这三个点的标号标号，因此修改这三个点的标号:（3）比较所有比较所有T标号，标号，T（v2）最小，因此令）最小，因此令P（v2）=6，并记录路径并记录路径（v1，

22、v2）。660,min)1(),(min)(1222 lvPvTvT10100,min)1(),(min)(1333 lvPvTvT12120,min)1(),(min)(1444 lvPvTvT（4）考察点考察点v2，由于（，由于（v2，v3），（），（v2，v5）属于）属于E，且，且v3，v5为为T标号，因此修改这两个点的标号标号，因此修改这两个点的标号:（5）比较所有比较所有T标号，标号，T（v3）最小，因此令）最小，因此令P（v3）=9，并记录路径并记录路径（v2，v3）。（6）考察点考察点v3，由于，由于(v3，v4)，(v3，v5)，(v3，v6)属于属于E，且，且v4，v5，v6

23、为为T标号，因此修改这三个点的标号：标号，因此修改这三个点的标号：（7）比较所有比较所有T标号，标号，T（v4）最小，因此令）最小，因此令P（v4）=12，且记录路径且记录路径（v1，v4）。936,10min)(),(min)(23233 lvPvTvT20146,min)(),(min)(25255 lvPvTvT1259,12min)(),(min)(34344 lvPvTvT1679,min)(),(min)(36366 lvPvTvT1899,20min)(),(min)(35355 lvPvTvT（9）比较所有比较所有T标号，标号，T（v6）最小，因此令）最小，因此令P（v6）=1

24、6，记录路径记录路径（v3，v6）。（8）考察点考察点v4，由于（，由于（v4，v6）属于）属于E，且，且v6为为T标号，标号，因此修改这一个点的标号：因此修改这一个点的标号：16512,16min)(),(min)(46466 lvPvTvT（10）考察点考察点v6，由于（，由于（v6，v5），（），（v6，v7）属于）属于E，且且v5，v7为为T标号，因此修改这两个点的标号：标号，因此修改这两个点的标号：（11）比较所有比较所有T标号，标号，T（v5）最小，因此令）最小，因此令P（v5）=18，记录路径记录路径（v3，v5）。18816,18min)(),(min)(65655 lvPvT

25、vT321616,min)(),(min)(67677 lvPvTvT（12）考察点考察点v5，由于（，由于（v5，v7）属于）属于E，且，且v7为为T标号，标号，因此修改这个点的标号：因此修改这个点的标号：（13）因为只有一个因为只有一个T标号，所以令标号，所以令P（v7）=29，记录路径记录路径（v5,v7）。291118,32min)(),(min)(57577 lvPvTvTV1V2V3V4V5V6V76101232557691481116（0）（6）（9）（12）（16）（20）（29）所以，最短路所以，最短路为为v1v2 v3 v5 v7，距离为，距离为29。三、逐次逼近法三、逐次

26、逼近法求指定点求指定点v1到其他任意点到其他任意点vt的最短路（边的权可以的最短路（边的权可以为负）为负）步骤：步骤：（1）令）令（2）（3）当进行到第）当进行到第t步时，若出现步时，若出现则停止，则停止，即为即为v1到各点的最短路长。到各点的最短路长。),2,1(1)1(1njlPjj ),3,2(min)1(1)(1 klPPijkiikj),2,1()1(1)(1njPPtjtj ),2,1()(1njPtj 的的所所有有道道路路中中的的最最短短路路条条边边到到最最多多经经过过表表示示jkjvkvP1)(1V1V2V3V4V5V6V725-3-274643-1-324V8求下图中求下图中

27、v1到其他所有点的最短路到其他所有点的最短路：（1）当当k=1时，时，0)1(11 P 2)1(12 P 5)1(13 P 3)1(14 P )1(18)1(17)1(16)1(15 PPPPV1V2V3V4V5V6V725-3-274643-1-324V86)3(),3(,42min,min85)1(1865)1(1625)1(12)2(15 lPlPlPP112,65min,min76)1(1736)1(13)2(16 lPlPP min87)1(18)2(17lPP min68)1(16)2(18lPP（2）当当k=2时，时，0)2(11 P2)2(12 P043),2(2,50min,

28、min43)1(1423)1(1213)1(11)2(13lPlPlPP37),3(0min,min74)1(1714)1(11)2(14 lPlPP（0）（2）（5）（-3）（+）（+）（+）（+）（3）当当k=3时，时，0)3(11 P2)3(12 P043),2(2,30min,min43)2(1423)2(1213)2(11)3(13 lPlPlPP37),3(0min,min74)2(1714)2(11)3(14 lPlPP63),3(11,42min,min85)2(1865)2(1625)2(12)3(15 lPlPlPP )1(minmin87)2(18)3(17lPP1541

29、1minmin68)2(16)3(18 lPP62,60min,min76)2(1736)2(13)3(16 lPlPPV1V2V3V4V5V6V725-3-274643-1-324V8（0）（2）（0）（-3）（6）（+）（+）（11）（4）当当k=4时，时，0)4(11 P2)4(12 P043),2(2,30min,min43)3(1423)3(1213)3(11)4(13 lPlPlPP37),3(0min,min74)3(1714)3(11)4(14 lPlPP3315),3(6,42min,min85)3(1865)3(1625)3(12)4(15lPlPlPP14)1(15min

30、min87)3(18)4(17 lPP1046minmin68)3(16)4(18 lPP62,60min,min76)3(1736)3(13)4(16 lPlPPV1V2V3V4V5V6V725-3-274643-1-324V8（0）（2）（0）（-3）（6）（15）（+）（6）（5）当当k=5时，时，0)5(11 P2)5(12 P043),2(2,50min,min43)4(1423)4(1213)4(11)5(13lPlPlPP37),3(0min,min74)4(1714)4(11)5(14 lPlPP3310),3(6,42min,min85)4(1865)4(1625)4(12)

31、5(15lPlPlPP9)1(10minmin87)4(18)5(17 lPP1046minmin68)4(16)5(18 lPP6214,60min,min76)4(1736)4(13)5(16 lPlPPV1V2V3V4V5V6V725-3-274643-1-324V8（0）（2）（0）（-3）（3）（10）（14）（6）（6）当当k=6时，时，0)6(11 P2)6(12 P043),2(2,30min,min43)5(1423)5(1213)5(11)6(13 lPlPlPP37),3(0min,min74)5(1714)5(11)6(14 lPlPP3310),3(6,42min,m

32、in85)5(1865)5(1625)5(12)6(15lPlPlPP9)1(10minmin87)5(18)6(17 lPP1046minmin68)5(16)6(18 lPP6214,60min,min76)5(1736)5(13)6(16 lPlPPV1V2V3V4V5V6V725-3-274643-1-324V8（0）（2）（0）（-3）（10）（9）（6）（3）v1000000v2222222v3500000v4-3-3-3-3-3-3v566333v6116666v71499v815101010 逆推法推出逆推法推出v1到到vt的最短路的最短路，如考察，如考察v1到到v7的最短路，

33、的最短路，依次找到点依次找到点v8,v6,v3,v2,v1。)1(1 jP)2(1 jP)3(1 jP)4(1 jP)5(1 jP)6(1 jP四、四、Floyd算法算法求网络上任意两点间的最短路。求网络上任意两点间的最短路。其他其他 ),(EvvldjiijijnnijdD )(令网络的权矩阵为：令网络的权矩阵为：算法的基本步骤为：算法的基本步骤为：（1）输入权矩阵）输入权矩阵DD)0(（2）计算）计算),3,2,1()()()(nkdDnnkijk 其中其中 ,min)1()1()1()(kkjkikkijkijdddd（3）中元素中元素 就是就是 到到 的最短路长。的最短路长。)()()

34、(nnnijndD )(nijdivjvV1V2V3V4V52524213102648 0442406282032210052150)0(DD 044240)3()7(2820322)7()6(052150413412214213)1(D求下图中任意两点间的最短路：求下图中任意两点间的最短路：0442)7(40372)5(203227605)7(2150521413412325214213125)2(D 0442)6(403)6(25203227605)6(21)4(053141341323252142131325132)3(D 04426403625203227605621405314134

35、1323252142131325132)4(D 0442640362520322)6(6056214053141341323252542131325132)5(D五、最短路问题的应用举例五、最短路问题的应用举例1.设备更新问题设备更新问题 某工厂使用一台设备，每年年初工厂都要作出某工厂使用一台设备，每年年初工厂都要作出决定，如果继续使用旧的，要付维修费；若购买一决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。试制定一个台新设备，要付购买费。试制定一个5 5年计划，使年计划，使总支出最少。总支出最少。项目项目第第1 1年年第第2 2年年第第3 3年年第第4 4年年第第5 5年年

36、购买费购买费11111212131314141414役龄役龄0-10-11-21-22-32-33-43-44-54-5维修费维修费5 56 68 811111818残值残值4 43 32 21 10 0 转化为下图所示的求转化为下图所示的求v1v1到到v6v6的最短路问题：的最短路问题：V1V2V3V4V5V612131415151928405920294121302212+（5+6+8）-2=2914+（5+6）-3=22 可以用可以用DijkstraDijkstra法求解。法求解。2.选址问题选址问题 已知某地区的交通网络如下图所示，其中点代已知某地区的交通网络如下图所示，其中点代表居民

37、小区，边表示公路，表居民小区，边表示公路，为小区间公路的距离，为小区间公路的距离，问区中心医院应建在哪个小区，可使离医院最远的问区中心医院应建在哪个小区，可使离医院最远的小区就诊时所走的路程最近？小区就诊时所走的路程最近？ijlV1V3V2V4V6V730152520601815V530这是求任意两点间最短路的问题，可以用这是求任意两点间最短路的问题，可以用FloydFloyd法求解。法求解。151501825150306018300202560200201520030300)0(DD 151501825150306018300202560200201520030300)1(D 1515018

38、2515)45(030601830020256020020)50(1520030)45()50(300)2(D 15150)85(18251545)85(03060)80()110(1830020)40()70(2560200205015)80()40(2003045)110()70(50300)3(D 15150)48(18251545)48(030)50()70()100(1830020407025)50(200205015)70(402003045)100(7050300)4(D 151504818251545480305070100183002040702550200205015704

39、020030451007050300)5(D )30(15)63()33()40()30()60(1504818251545)63(4803050)63()93()33(1830020)33()63()40(25502002050)30(15)63()33(20030)60(45)93()63(50300)6(D 30156333403060150481825154563480305063933318300203363402550200205030156333200306045936350300)7(Dmin93635063934863所以应该把医院设在所以应该把医院设在v6处，此时处，此时v

40、5距离医院最远，距离为距离医院最远，距离为48。第四节第四节最最 大大 流流 问问 题题1.容量网络容量网络 一、最大流相关概念一、最大流相关概念3511 42352vsv1v3v4vt 给给定一个有向图定一个有向图G G(V,E)(V,E)，其中仅有一个点的入其中仅有一个点的入次为零次为零称为称为发点（源）发点（源），记为记为v vs s，仅有仅有一个点的出次一个点的出次为零称为为零称为收点（汇）收点（汇），记为记为v vt t，其余点称为其余点称为中间点中间点。对于对于G G中的每一个弧中的每一个弧(v vi i,v,vj j)，相应相应地给地给一个数一个数c cijij（c cijij0

41、0），），称为弧称为弧(v vi i,v,vj j)的的容量容量。我们把这样的。我们把这样的G G称为称为容量网络容量网络，记为记为G G(V,E,C)(V,E,C)。一、最大流相关概念一、最大流相关概念2.流流 所谓网络上的所谓网络上的流流，是指定义在弧集，是指定义在弧集E E上的函数上的函数f ff(vf(vi i,v,vj j)，并称并称f(vf(vi i,v,vj j)为弧为弧(v vi i,v,vj j)上的上的流量流量，简记，简记为为f fijij。3,15,21,01,0 4,12,23,15,22,1vsv2v1v3v4vt标示方式：每条边上标示两个数字，第一个是容量，第二标示

42、方式：每条边上标示两个数字，第一个是容量，第二是流量是流量一、最大流相关概念一、最大流相关概念3.可行流可行流可行流可行流是指满足如下条件的流：是指满足如下条件的流：（1）容量限制条件容量限制条件：对：对G中每条边中每条边(vi,vj),有：有：ijijcf 0（2）平衡条件平衡条件：对中间点，有：对中间点，有：kkijijff（即中间点（即中间点vi的物资输入量等于输出量）的物资输入量等于输出量）对收点对收点vt与发点与发点vs，有：，有：（即（即vs发出的物资总量等于发出的物资总量等于vt接收的物资总量），接收的物资总量），W是网络的总流量。是网络的总流量。Wffjjtisi容量网络中可行

43、流总是存在的。容量网络中可行流总是存在的。一、最大流相关概念一、最大流相关概念4.最大流最大流所谓最大流问题就是在容量网络中所谓最大流问题就是在容量网络中寻找流量最大的可行流寻找流量最大的可行流。最大流问题实际上是一个线性规划问题：最大流问题实际上是一个线性规划问题：ijijcf 0),(tisiffkkijijWffjjtisis.ts.t.Wz min 任一个网络任一个网络G中，从中，从vs到到vt的最大流的的最大流的流量等于分离流量等于分离vs、vt的最小割的容量。的最小割的容量。二、最大流二、最大流-最小割定理最小割定理三、求最大流的标号算法三、求最大流的标号算法通过标号寻找可增广链通过标号寻找可增广链调整流量调整流量