第八章 图与网络分析PPT讲稿.ppt

《第八章 图与网络分析PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《第八章 图与网络分析PPT讲稿.ppt（83页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第八章 图与网络分析第1页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第2页，共83页，编辑于2022年，星期三BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题1图与网络的基本知识环球旅行问题环球旅行问题第3页，共83页，编辑于2022年，星期三一个图是由点集V=vj和V中元素的无序对的一个集合E=ek构成的二元组，记为G=(V,E),其中V 中的元素vj 叫做顶点，V表示图G的点集合；E中的元素ek 叫做边，E 表示图 G 的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图1 1

2、定义定义1 1图及其分类第4页，共83页，编辑于2022年，星期三如果一个图是由点和边所构成的，则称其为无向图，记作G=(V,E)，连接点的边记作vi,vj,或者vj,vi。如果一个图是由点和弧所构成的，那么称它为有向图，记作D=(V,A)，其中V 表示有向图D 的点集合，A 表示有向图D 的弧集合。一条方向从vi指向vj 的弧，记作(vi,vj)。v4v6v1v2v3v5V=v1,v2,v3,v4,v5,v6，A=(v1,v3),(v2,v1),(v2,v3),(v2,v5),(v3,v5),(v4,v5),(v5,v4),(v5,v6)图图2图及其分类第5页，共83页，编辑于2022年，星

3、期三一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义定义2 2定义定义3 3图及其分类第6页，共83页，编辑于2022年，星期三定义定义4 4图G=(V,E)的点集V可以分为两个非空子集X，Y，即XY=V,XY=，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G=(X,Y,E)。X:v1,v3,v5Y:v2,v4,v6v

4、1v3v5v6v4v2图及其分类第7页，共83页，编辑于2022年，星期三v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。以点v为端点的边的个数称为点v 的度（次），记作 。图中d(v1)=4，d(v6)=4（环计两度）定义定义5 5顶点的次第8页，共83页，编辑于2022年，星期三有向图中，以vi为始点的边数称为点vi的出次，用 表示；以vi为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。

5、定理定理1 1定理定理2 2所有顶点度数之和等于所有边数的2倍。在任一图中，奇点的个数必为偶数。定义定义6 6顶点的次第9页，共83页，编辑于2022年，星期三图G=(V,E)，若E是E的子集，V是V的子集，且E中的边仅与V中的顶点相关联，则称G=(V,E)是G的一个子图。特别是，若V=V，则G称为G的生成子图(支撑子图)。v1v2v3v4v5v6v7e1e2e3e4e5e6e7e8e9e10e11(a)e5e7v1v2v5v6v7e1e6e8(b)子图v1v2v3v4v5v6v7e1e6e7e9e10e11(c)支撑子图定义定义7 7子图第10页，共83页，编辑于2022年，星期三在实际应用

6、中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指定两个点，一个称为始点（或发点），记作v1，一个称为终点（或收点），记作vn，其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权”。通常把这种赋权的图称为网络。定义定义8 8无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。点边列中没有重复的点和重复边者为初等链。连通图第11页，共83页，编辑于2022年，星期三连通图无向图G中，连结vi0与v

7、ik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。定义定义9 9定义定义1010一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。第12页，共83页，编辑于2022年，星期三对于网络（赋权图）G=（V,E）,其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。设图G=（V,E）中顶点的个数为n，构造一个矩阵 ，其中：

8、称矩阵A为网络G的邻接矩阵。定义定义1111定义定义1212图的矩阵表示当G为无向图时，邻接矩阵为对称矩阵。第13页，共83页，编辑于2022年，星期三例例权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示第14页，共83页，编辑于2022年，星期三欧拉回路与中国邮路问题定义定义1313 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图(E图)。在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。定理定理3 3无向连通图G是欧拉图，当且

9、仅当G中无奇点。定理定理4 4连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。第15页，共83页，编辑于2022年，星期三欧拉回路与中国邮路问题定理定理5 5已知图G*=G+E1无奇点，则 最小的充分必要条件为：(1)每条边最多重复一次；(2)对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。第16页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第17页，共83页，编辑于2022年，星期三2树ACBEDGFIHJ KNML运动员乒乓球单打比赛第18页，共83页，编辑于2022年，星期三树的概念和性质定理定理6 6定义定

10、义1414连通且不含圈的无向图称为树。树中次为1的点称为树叶，次大于1的点称为分枝点。图T=(V,E),|V|=n,|E|=m，则下列关于树的说法是等价的。(1)T是一个树。(2)T无圈，且m=n-1。(3)T连通，且m=n-1。(4)T无圈，但每加一新边即得惟一一个圈。(5)T连通，但任舍去一边就不连通。(6)T中任意两点，有惟一链相连。第19页，共83页，编辑于2022年，星期三一个图G 有生成树的充要条件是G 是连通图。v1v2v3v4v5v1v2v3v4v5设图 是图G=(V,E)G=(V,E)的一支撑子图，如果图 是一个树,那么称K K 是G G 的一个生成树（支撑树），或简称为图G

11、 G 的树。图G G中属于生成树的边称为树枝，不在生成树中的边称为弦。定义定义1515定理定理7 7图的生成树第20页，共83页，编辑于2022年，星期三（一）（一）避圈法避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。第21页，共83页，编辑于2022年，星期三e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4第22页，共83页，编辑于2022年，星期三

12、（二）（二）破圈法破圈法第23页，共83页，编辑于2022年，星期三用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第24页，共83页，编辑于2022年，星期三最小生成树问题定义定义1616如果图 是图G的一个生成树，那么称E1上所有边的权的和为生成树T 的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G 的所有生成树T 中的权最小，即那么称T*是G 的最小生成树。某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。

13、v1v2v3v4v5v66515723445v1v2v3v4v5v612344第25页，共83页，编辑于2022年，星期三v1v2v3v4v514231352根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。第26页，共83页，编辑于2022年，星期三|最小树的两种算法 算法1（Kruskal算法）算法2（破圈法）第27页，共83页，编辑于2022年，星期三|树根及其应用定义定义1717若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义定义1818有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。定义定义

14、1919在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。第28页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第29页，共83页，编辑于2022年，星期三最短路的一般提法为：设 为连通图，图中各边 有权 （表示 之间没有边），为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即：最小。3最短路问题(一一)狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法适用于wij00，给出了从vs到任意一个点vj的最短路。Dijkstr

15、a算法是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。第30页，共83页，编辑于2022年，星期三算法步骤：算法步骤：1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号，2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。第31页，共83

16、页，编辑于2022年，星期三例例9用Dijkstra算法求下图从v1到v8的最短路。解解（1）首先给v1以P标号，给其余所有点T标号。（2）（3）（4）v1v7v2v3v6v4v8v54594546467157比较所有T标号，T(v2)最小，令P(v2)=4，并记录路径(v1,v2)第32页，共83页，编辑于2022年，星期三比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3)比较所有T标号，T(v5)最小，令P(v5)=8,并记录路径(v2,v3)比较所有T标号，T(v4)最小，令P(v4)=9,并记录路径(v2,v4)比较所有T标号，T(v6)最小，令P(v6)=13

17、,并记录路径(v5,v6)第33页，共83页，编辑于2022年，星期三比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v7,v8)因为只有一个T标号T(v8)最小，令P(v8)=15,并记录路径(v7,v8)，v1到v8之最短路为:v2v1v7v5v8 Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。第34页，共83页，编辑于2022年，星期三v1v9v8v7v6v5v4v3v23333342.55222140如图，有一批货物要从v1运到v9，弧旁数字表示该段路长，求最短运输路线。标号法练习第35页，共83页，编辑于2022

18、年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 3第36页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 3第37页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03

19、34 4第38页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 4第39页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 45 5第40页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34

20、42.52.55 52 22 22 21 14 40 03 34 45 5第41页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 46 66 65 5第42页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 46 66 65 5第43页，共83页，编辑于2022年，星期三v1v1v

21、9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 46 67 75 56 6第44页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 46 67 75 56 68.58.5第45页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.5

22、2.55 52 22 22 21 14 40 03 34 46 67 75 56 68.58.59 9第46页，共83页，编辑于2022年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 33 33 33 33 34 42.52.55 52 22 22 21 14 40 03 34 46 67 75 56 68.58.59 9第47页，共83页，编辑于2022年，星期三练习：练习：求从求从v1到到v8的的最短最短路路(0)(1,1)(1,3)(3,5)(2,6)(5,10)(5,9)(5,12)第48页，共83页，编辑于2022年，星期三标号法练习求从求从v1

23、到到v8的最短路的最短路(2,6)第49页，共83页，编辑于2022年，星期三算法的基本思路与步骤：首先：设任一点vi到任一点vj都有一条弧。显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令 即用v1到vj的直接距离做初始解。第二步，使用递推公式：求 ，当进行到第t步，若出现则停止计算，即为v1到各点的最短路长。（二）逐次逼近法（二）逐次逼近法第50页，共83页，编辑于2022年，星期三例例10求图中求

24、图中v v1 1到各点的最短路到各点的最短路v1v2v3v4v5v6v7v85-324431-217-324第51页，共83页，编辑于2022年，星期三解：初始条件为第一轮迭代：第52页，共83页，编辑于2022年，星期三类似可得v1v2v3v4v5v6v7v8P1j(1)P1j(2)P1j(3)P1j(4)P1j(5)P1j(6)v1025-3000000v20-2422222-5v306500000v44 0-3-3-3-3-3-3v5066333v6-3 04116666v77201499v83-1015101010表中最后一列数字表示v1到各点的最短路长第53页，共83页，编辑于202

25、2年，星期三例11 求：5年内，哪些年初购置新设备，使5年内的总费用最小。解：（1）分析：可行的购置方案（更新计划）是很多的，如：1)每 年 购 置 一 台 新 的，则 对 应 的 费 用 为：11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。第i年度 12345购置费1111121213设备役龄0-11-22-33-44-5维修费用 5681118第54页，共83页，编辑于2022年，星期三 （2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步

26、骤：1）画赋权有向图：设 vi 表示第i年初，(vi,vj)表示第i 年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从v1 到v6的一条路。2）求解（标号法）第55页，共83页，编辑于2022年，星期三W12=11+5=16W13=11+5+6=22W14=11+5+6+8=30W15=11+5+6+8+11=41W16=11+5+6+8+11+18=59W23=11+5=16W24=11+5+6=22W25=11+5+6+8=30W26=11+5+6+8+11=41W45=12+5=17W46=12+5+6=23W56=13+5=18W34=12+

27、5=17W35=12+5+6=23W36=12+5+6+8=31第56页，共83页，编辑于2022年，星期三（三）（三）FloydFloyd算法算法可直接求出网络中任意两点间的最短路；第57页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第58页，共83页，编辑于2022年，星期三4最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要

28、组成部分。第59页，共83页，编辑于2022年，星期三问题引入vsv2v3v4v1vt33244242321上图可看作输油管道网，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大?第60页，共83页，编辑于2022年，星期三网络D上的流，是指定义在弧集合E上的一个函数其中f(vi,vj)=fij 叫做弧(vi，vj)上的流量。最大流有关概念定义定义2020设一个赋权有向图D=（V,E）,在V中指定一个发点vs和一个收点vt,其它的点叫做中间点。对于D中的每一个弧（vi,vj）E,都有一个非负数c

29、ij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。第61页，共83页，编辑于2022年，星期三称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi,vj）E有0 fij cij。（2）平衡条件：对于发点vs，有对于收点vt，有对于中间点，有可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。第62页，共83页，编辑于2022年，星期三定义定义2121容量网络G=(V,E,C),vs,vt为发、收点，若有边集E为E的子集，将G分为两个子图G1,G2，其顶点集合分别记S，S =V,

30、S =,vs,vt分属S，满足：G(V,E-E)不连通；E为E的真子集，而G(V,E-E)仍连通，则称E为G的割集，记E=(S,)。第63页，共83页，编辑于2022年，星期三最大流-最小流定理定理定理1111设f为网络G=(V,E,C)的任一可行流，流量为W，(S，)是分离vs,vt的任一割集，则有WC(S,)。定理定理1010(最大流-最小割定理)任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。第64页，共83页，编辑于2022年，星期三可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。定义定义2222容量网络G，若 为网络中从vs

31、到vt的一条链，给 定向为从vs到vt，上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，如果满足：则称 为从vs到vt 的关于f 的一条增广链即 中的每一条弧都是非饱和弧即 中的每一条弧都是非零流弧推论推论第65页，共83页，编辑于2022年，星期三求最大流的标号算法 设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。第66页，共83页

32、，编辑于2022年，星期三一、标号过程：1给发点vs 标号（0，+）。2取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 ，且 ，那么给vj 标号 ，其中：（2）如果边 ，且 ，那么给vj 标号 ，其中：3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。第67页，共83页，编辑于2022年，星期三二、调整过程设1令 2去掉所有标号，回到第一步，对可行流重新标号。第68页，共83页，编辑于2022年，星期三例：求下图所示网络中的最大流，弧旁数

33、为(3,1)v2v1v4vsvtv3(5,5)(5,1)(2,1)(5,4)(2,2)(5,5)(1,1)(2,0)第69页，共83页，编辑于2022年，星期三例：求下图所示网络中的最大流，弧旁数为(3,0)v2v1v4vsvtv3(3,3)(5,1)(2,1)(4,3)(2,2)(5,3)(2,1)(1,1)第70页，共83页，编辑于2022年，星期三例14求下图所示网络中的最大流，弧旁数为(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)图8-40第71页，共83页，编辑于2022年，星期三解.用标号

34、法。1.标号过程。1）首先给vs标号（0，+）2）看vs:在弧(vs,v1)上,fs2=2cs2=4,具备标号条件。故给v2标号(+vs,v2),其中v2=min(cs2-fs2),vs=min2,+=4.3）看v2:在弧(v2,v5)上,f25=0c25=3,具备标号条件。故给v5标号(+v2,2),其中v5=min3，2=2.vt类似前面的步骤，可由v4得到标号+v4，2 由于vt已得到标号，说明存在可增广链，所以标号过程结束。第72页，共83页，编辑于2022年，星期三(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5

35、(2,2)(4,2)（，+）（-v5，2）（+v1，2）（+v4，2）（+v2，2）（+vS，1）（+vs，2）图8-41第73页，共83页，编辑于2022年，星期三2.转入调整过程令=vt=2为调整量，从vt点开始，由逆可增广链方向按标号+v4,2找到点v4,令f4t=f4t+2。再由v4点标号+v1,2找到前一个点v1，并令f14=f14+2。按v1点标号找到点v5，由于标号为-v5,(v5,v1)为反向边，令f15=f15-2。由v5点的标号再找到v2，令f25=f25+2。由v2点找到vs，令fs2=fs2+2。调整过程结束，调整中的可增广链见图8-41中的粗线边，调整后的可行流见图8

36、-42第74页，共83页，编辑于2022年，星期三（，+）（+vS，1）图8-42(3,3)v2v1v4v6vsvtv3(3,0)(5,5)(3,2(5,4)(5,2)(2,2)(4,2)(3,3)v5(2,2)(4,2)重新开始标号过程，寻找可增广链，当标到v3点为+vs,1以后，与vs,v3点邻接的v1,v2,v6点都不满足标号条件，所以标号过程无法再继续，而vt点并未得到标号，如图8-42。这时W=fs1+fs2+fs3=f4t+f5t+f6t=11，即为最大流的流量，算法结束。第75页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用

37、流问题第76页，共83页，编辑于2022年，星期三5最小费用流问题 最小费用流问题的一般提法：已知容量网络G=(V,E,C)，每条边(vi,vj)除了已给出容量cij外，还给出了单位流量的费用dij(0)，记G=(V,E,C,d)。求G的一个可行流f=fij，使得流量W(f)=v，且总费用最小。d(f)=(vi,vj)Edijfij特别地，当要求f为最大流时，此问题即为最小费用最大流问题。最小费用流问题的常用算法有两种：(1)原始算法；(2)对偶算法。下面只介绍第二种算法，本算法是有效算法。第77页，共83页，编辑于2022年，星期三5最小费用流问题已知网络G=（V，E，C，d），f是G上的一

38、个可行流，为一条从vs到vt的增广链，称为链的费用。定义定义2424若 *是从vs到vt的增广链中费用最小的增广链，则称 *是最小费用增广链。定理定理1212若f是流量为W(f)的最小费用流，是关于f的从vs到vt的一条最小费用可增广链，则f经过 调整流量得到新可行流f(记为f=f)，一定是流量为W(f)+的可行流中的最小费用流。第78页，共83页，编辑于2022年，星期三1.当 ，令寻找关于f 的最小费用增广链：构造一个关于f 的赋权有向图L(f)，其顶点是原网络G的顶点，而将G中的每一条弧(vi,vj)变成两个相反方向的弧（vi,vj）和(vj,vi)，并且定义图中弧的权lij为：在网络G

39、中寻找关于f 的最小费用增广链等价于在L(f)中寻求从vs 到vt 的最短路。2.当（vj,vi）为原来网络G中(vi,vj)的反向弧,令第79页，共83页，编辑于2022年，星期三步骤：（1）取零流为初始可行流，f(0)=0。（2）一般地，如果在第k-1步得到最小费用流 f(k-1)，则构造图 L(f(k-1)。（3）在L(f(k-1)中，寻求从vs到vt的最短路。若不存在最短路，则f(k-1)就是最小费用最大流；否则转(4)。（4）如果存在最短路，则在可行流f(k1)的图中得到与此最短路相对应的增广链，在增广链上，对f(k1)进行调整，调整量为：第80页，共83页，编辑于2022年，星期三

40、令得到新可行流f(k)。对f(k)重复上面步骤，返回（2）。例例16在在图8-48所示运输网络上求流量v为10的最小费用最大流，弧旁权是（cij,dij）（10,4）vsv2v3vtv1（5,2）（7,1）（2,6）（4,2）（10,3）（8,1）第81页，共83页，编辑于2022年，星期三4vsv2v3vtv1216231L(f(0)0vsv2v3vtv1550005f(1)2vsv2v3vtv1570005f(2)1L(f(1)4vsv2v3vtv1-2-1623-1d(f(1)=51+52+51=20d(f(2)=42+51+52+71=30第82页，共83页，编辑于2022年，星期三1L(f(2)4vsv2v3vtv1-2-1623-1-42vsv2v3vtv1570338f(3)d(f(3)=24+81+52+33+32+71=48f(3)即为所求的最小费用流。第83页，共83页，编辑于2022年，星期三