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

第八章 图与网络分析第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定义定义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年，星期三一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义定义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,v6v1v3v5v6v4v2图及其分类第7页，共83页，编辑于2022年，星期三v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。以点v为端点的边的个数称为点v 的度（次），记作 。图中d(v1)=4，d(v6)=4（环计两度）定义定义5 5顶点的次第8页，共83页，编辑于2022年，星期三有向图中，以vi为始点的边数称为点vi的出次，用 表示；以vi为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶点的出次之和。定理定理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年，星期三在实际应用中，给定一个图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与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为初等圈。定义定义9 9定义定义1010一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。第12页，共83页，编辑于2022年，星期三对于网络（赋权图）G=（V,E）,其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。设图G=（V,E）中顶点的个数为n，构造一个矩阵 ，其中：称矩阵A为网络G的邻接矩阵。定义定义1111定义定义1212图的矩阵表示当G为无向图时，邻接矩阵为对称矩阵。第13页，共83页，编辑于2022年，星期三例例权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示第14页，共83页，编辑于2022年，星期三欧拉回路与中国邮路问题定义定义1313 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路。具有欧拉回路的图称为欧拉图(E图)。在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。定理定理3 3无向连通图G是欧拉图，当且仅当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定义定义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 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年，星期三（二）（二）破圈法破圈法第23页，共83页，编辑于2022年，星期三用破圈法求出下图的一个生成树。v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8第24页，共83页，编辑于2022年，星期三最小生成树问题定义定义1616如果图 是图G的一个生成树，那么称E1上所有边的权的和为生成树T 的权，记作S(T)。如果图G的生成树T*的权S(T*)，在G 的所有生成树T 中的权最小，即那么称T*是G 的最小生成树。某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。v1v2v3v4v5v66515723445v1v2v3v4v5v612344第25页，共83页，编辑于2022年，星期三v1v2v3v4v514231352根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。第26页，共83页，编辑于2022年，星期三|最小树的两种算法 算法1（Kruskal算法）算法2（破圈法）第27页，共83页，编辑于2022年，星期三|树根及其应用定义定义1717若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义定义1818有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。定义定义1919在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。第28页，共83页，编辑于2022年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第29页，共83页，编辑于2022年，星期三最短路的一般提法为：设 为连通图，图中各边 有权 （表示 之间没有边），为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。即：最小。3最短路问题(一一)狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法适用于wij00，给出了从vs到任意一个点vj的最短路。Dijkstra算法是在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页，编辑于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,并记录路径(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年，星期三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 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 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年，星期三v1v1v9v9v8v8v7v7v6v6v5v5v4v4v3v3v2v23 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.52.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到到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求图中求图中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页，编辑于2022年，星期三例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）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。求解步骤：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+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)建立的“网络流理论”，是网络应用的重要组成部分。第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,都有一个非负数cij,叫做弧的容量。我们把这样的图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,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到vt的一条链，给 定向为从vs到vt，上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，如果满足：则称 为从vs到vt 的关于f 的一条增广链即 中的每一条弧都是非饱和弧即 中的每一条弧都是非零流弧推论推论第65页，共83页，编辑于2022年，星期三求最大流的标号算法 设已有一个可行流f，标号的方法可分为两步：第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。第66页，共83页，编辑于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年，星期三例：求下图所示网络中的最大流，弧旁数为(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年，星期三解.用标号法。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(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-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年，星期三本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题第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上的一个可行流，为一条从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中寻找关于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年，星期三令得到新可行流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年，星期三