《运筹学教学资料》运筹学第10-11章.ppt

Chapter10 图与网络分析(Graph Theory and Network Analysis),图的基本概念与模型树与图的最小树最短路问题网络的最大流,本章主要内容：,学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。,18世纪，Knigsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”,1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文。,七桥问题,图的基本概念与模型,中国邮路问题,一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。,1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。,图的基本概念与模型,Hamilton图,游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。,问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。,the dodecahedron is Hamiltonian,显然这样的路线存在且不唯一,图的基本概念与模型,在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于44，55，或88的棋盘上马的跳动如何？,图的基本概念与模型,幻方问题,图的基本概念与模型,某团体举行舞会，其中有n 个男士与n 个女士，每个男士恰好认识 r 个女士，每个女士也恰好认识 r 个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。,比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识,鸽笼原理和Ramsey数,图的基本概念与模型,四色猜想,能否用四种颜色给地图染色，使相邻的国家有不同的颜色。,问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。,图的基本概念与模型,Mbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。,Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。,平面图与网络,图的基本概念与模型,n-方体Qn,n方体,n 维立方体n=3 的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。,次，奇点，偶点，孤立点,与某一个点vi相关联的边的数目称为点vi的次（也叫做度），记作d(vi)。右图中d(v1),d(v3)=5,d(v5)=1。次为奇数的点称作奇点，次为偶数的点称作偶点，次为1的点称为悬挂点，次为0的点称作孤立点。,图的次:一个图的次等于各点的次之和。,图的基本概念与模型,链，圈，连通图,图中某些点和边的交替序列，若其中各边互不相同，且对任意vi,t-1和vit均相邻称为链。用表示：,起点与终点重合的链称作圈。如果每一对顶点之间至少存在一条链，称这样的图为连通图，否则称图不连通。,图的基本概念与模型,二部图（偶图）,图G=(V,E)的点集V可以分为两各非空子集X，Y，集XY=V,XY=,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。,(a),(b),(c),(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。,图的基本概念与模型,完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,n,K3,3 K2,4,G2,G1,G2,G1,G2,G1,网络（赋权图）,设图G（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。,图的基本概念与模型,出次与入次,有向图中，以vi为始点的边数称为点vi的出次，用d+(vi)表示；以vi为终点的边数称为点vi 的入次，用表示d-(vi)；vi 点的出次和入次之和就是该点的次。,有向图中，所有顶点的入次之和等于所有顶点的出次之和。,图的基本概念与模型,一个图是二部图当且仅当它不含奇圈。,设G 是一个简单图，若(G)2，则G 中必含有圈。,设G 是简单图，若(G)3,则G 必有偶圈。,设有2n 个电话交换台，每个台与至少n 个台有直通线路，则该交换系统中任二台均可实现通话。,回答：,图的基本性质：,定理1 任何图中，顶点次数之和等于所有边数的2倍。,定理2 任何图中，次为奇数的顶点必为偶数个。,证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数的总和等于边数的2倍。,证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：,2m为偶数，且偶点的次之和 也为偶数，所以 必为偶数，即奇数点的个数必为偶数。,图的基本概念与模型,图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等,1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中,图的基本概念与模型,2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:,3.权矩阵,对于赋权图G=(V,E),其中边 有权,构造矩阵B=(bij)nn 其中：,图的基本概念与模型,下图所表示的图可以构造邻接矩阵A如下,图的基本概念与模型,例1,v1v2v3v4v5v6v7v8,下图所表示的图可以构造邻接矩阵M如下:,M=（mij）=,1 0 1 0 0 0 0 0 0 0 0 01 1 0 0 1 0 0 0 0 0 0 00 1 0 0 0 1 1 1 0 0 0 00 0 0 0 0 0 0 0 1 0 0 10 0 1 1 1 1 0 0 0 0 0 00 0 0 0 0 0 0 0 1 1 0 00 0 0 0 0 0 0 0 0 1 1 10 0 0 1 0 0 1 1 0 0 0 0,图的基本概念与模型,例2,下图所表示的图可以构造权矩阵B如下:,图的基本概念与模型,例3,树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。,乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。,运动员,树与图的最小树,某企业的组织机构图也可用树图表示。,树与图的最小树,树是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点。具有k个连通分支的不包含圈的图称为k-树，或森林。下是具有六个顶点的树，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。,树：无圈的连通图即为树,性质1：任何树中必存在次为1的点。性质2：n 个顶点的树必有n-1 条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。,树与图的最小树,图的最小部分树(支撑树),如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝。一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。,G1,G2,树与图的最小树,(赋权)图中求最小树的方法：破圈法和避圈法,破圈法：任取一圈，去掉圈中最长边，直到无圈。,v1,v2,v3,v4,v5,v6,4,3,5,2,1,边数n-1=5,树与图的最小树,得到最小树：,Min C(T)=15,树与图的最小树,避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。,树与图的最小树,v1,v2,v3,v4,v5,v6,4,3,5,2,1,Min C(T)=15,树与图的最小树,10.3 最短路问题,如何用最短的线路将三部电话连起来？此问题可抽象为设ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如ABAC）。,A,B,C,最短路问题,A,B,C,P,但若增加一个周转站（新点P），连接4点的新网络的最短路线为PAPBPC。最短新路径之长比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。,最短路问题,问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。,最短路问题,渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。,最短路问题,例1,定义：1）人M（Man），狼W（Wolf），羊G（Goat），草H（Hay）2）点 vi 表示河岸的状态3）边 ek 表示由状态 vi 经一次渡河到状态 vj 4）权边 ek 上的权定为 1,我们可以得到下面的加权有向图,最短路问题,状态说明：v1,u1=(M,W,G,H);v2,u2=(M,W,G);v3,u3=(M,W,H);v4,u4=(M,G,H);v5,u5=(M,G),此游戏转化为在下面的二部图中求从 v1 到 u1 的最短路问题。,v1,v2,v3,v4,v5,u5,u4,u3,u2,u1,最短路问题,求最短路有两种算法:,狄克斯屈拉(Dijkstra)标号算法 逐次逼近算法,最短路问题,狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列 vs，v1.vn-1，vn 是从vs到vt间的最短路，则序列 vs，v1.vn-1 必为从vs 到vn-1的最短路。,假定v1v2 v3 v4是v1 v4的最短路，则v1 v2 v3一定是v1 v3的最短路，v2 v3 v4也一定是v2 v4的最短路。,最短路问题,Dijkstra算法基本步骤,Dijkstra算法的基本思想是从vs出发，逐步地向外探寻最短路，采用标号法。执行过程中，与每个点对应，记录下一个数（称为这个点的标号），它或者表示从vs到该点的最短路长（称为P标号），或者是从vs到该点的最短路长的上界（称为T标号）。算法每一步都把某个顶点的T 标号改为P 标号，当终点vt 得到 P 标号时，计算结束。最多n-1步。,最短路问题,网络图的最短路图的起点是vs，终点是vt，以vi为起点vj为终点的弧记为(i,j)，距离为dij。,P标号(点标号)：b(j)起点vs到点vj的最短路长；T标号(边标号)：k(i,j)=b(i)+dij。,最短路问题,步骤：,2.找出所有vi已标号vj未标号的弧集合 B=(i,j)如果这样的弧不存在或vt已标号则计算结束；,3.计算集合B中弧k(i，j)=b(i)+dij的标号;,4.选一个点标号 在终点vl处标号b(l),返回到第2步。,1.令起点的标号；b(s)0。,最短路问题,求连接 vs、vt 的最短路.,开始，给vs以 P 标号，P(vs)=0,其余各点给 T 标号 T(vi)=+.,Step 1:,迭代 1,Dijkstra算法基本步骤：,例2,最短路问题,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,2,4,5,迭代 1,考察vs,T(v2)=minT(v2),P(vs)+ws2=min+,0+5=5,T(v1)=minT(v1),P(vs)+ws1=min+,0+2=2,最短路问题,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,2,4,5,即 P(vi)=minT(vi).,当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.,-,2,迭代 1,全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs,v1).,最短路问题,9,4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,迭代 2,考察v1,T(v4)=minT(v4),P(v1)+w14=min+,2+7=9,T(v2)=minT(v2),P(v1)+w12=min5,2+2=4,最短路问题,4,4,迭代 2,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,-,-,全部 T 标号中,T(v2),T(v3)最小,令P(v2)=4,P(v3)=4,记录路径(v1,v2),(v1,v4),.,最短路问题,7,迭代 3,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,最短路问题,7,迭代 3,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,-,最短路问题,迭代 4,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,8,14,最短路问题,迭代 4,8,-,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,最短路问题,迭代 5,13,若 vi 为刚得到 P 标号的点,考虑这样的点 vj:(vi,vj)E 且vj 为 T 标号。,Step 2:,对vj的T 标号进行如下更改T(vj)=minT(vj),P(vi)+wij,最短路问题,迭代 5,13,比较所有具有 T 标号的点，把最小者改为P 标号，,Step 3:,即 P(vi)=minT(vi).,当存在两个以上最小者时,可同时改为P 标号。若全部点为P标号,则停止。否则用vi代替vi转step 2.,-,最短路问题,最短路,Dijkstra算法不仅找到了所求最短路，而且找到了从 vs 点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,最短路问题,从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。,最短路问题,算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。,如右图所示中按dijkstra算法可得P(v1)=5为从vsv1的最短路长显然是错误的，从vsv2v1路长只有3。,v2,vs,v1,5,-5,8,最短路问题,例2,Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找v0到vn的最短路，但限于最短路只允许有一条边（弧），其距离记为d1(v0,vn).简记为d 1(vn)。第二次逼近，再找v0到vn的最短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为d 2(vn)。到第m次逼近,d m(vn)表示由v0到vn的不超过m条边（弧）组成的最短路的距离。最多p-1次。,网络有负权的最短路,最短路问题,Ford算法基本步骤：,(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).,解：d1(v0)=0,d1(v1)=2,d1(v2)=1,d1(v3)=-2.,0,2,1,-2,第一次逼近,最短路问题,(2)令,解：d2(v1)=min d1(v1)+w(v1,v1),d1(v2)+w(v2,v1),d1(v3)+w(v3,v1),0,2,1,-2,当vi,v 为同一个点时，有w(v,vi)=0.,=min 2+0,1+,-2+3=1.,1,d2(v2)=min d1(v1)+w(v1,v2),d1(v2)+w(v2,v2),d1(v3)+w(v3,v2),=min 2-2,1+0,-2+=0.,0,d2(v3)=min d1(v1)+w(v1,v3),d1(v2)+w(v2,v3),d1(v3)+w(v3,v3),=min 2+,1+1,-2+0=-2.,第二次逼近,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,解：d3(v1)=min d2(v1)+w(v1,v1),d2(v2)+w(v2,v1),d2(v3)+w(v3,v1),0,1,0,-2,=min 1+0,0+,-2+3=1.,d3(v2)=min d2(v1)+w(v1,v2),d2(v2)+w(v2,v2),d2(v3)+w(v3,v2),=min 1-2,0+0,-2+=-1.,-1,d3(v3)=min d2(v1)+w(v1,v3),d2(v2)+w(v2,v3),d2(v3)+w(v3,v3),=min 1+,0+1,-2+0=-2.,第三次逼近,(2)令,当vi,v 为同一个点时，有w(v,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,最后解得：d3(v1)=1，d3(v2)=-1，d3(v3)=-2.,0,1,-1,-2,即v0到v1最短路长度为 d3(v1)=1，最短路为v0,v3,v1.,即v0到v2最短路长度为 d3(v2)=-1,最短路为v0,v3,v1,v2.,即v0到v3最短路长度为 d3(v3)=-2,最短路为v0,v3.,最短路问题,Ford算法基本步骤：,(1)令m=1,令d1(v0)=0,d1(vi)=w(v0,vi).,(2)令,当vi,v 为同一个点时，有w(v,vi)=0.,(3)若m+1=p 则停止。否则m=m+1,转(2).,最短路问题,某些问题中，要求网络上任意两点间的最短路。这类问题可以用 Dijkstra 算法依次改变起点的办法计算，但比较繁琐。而 F1oyd 方法(1962年)可直接求出网络中任意两点间的最短路。,令网络的权矩阵为,三、Floyd算法,其中,最短路问题,权矩阵：,图中有四条无向边，每条均可化为两条方向相反的有向边。,则得权矩阵为：,最短路问题,(1)输入权矩阵 D(0)=D;(2)计算 其中(3)中元素,Floyd算法基本步骤：,就是vi到vj的,最短路长.,最短路问题,计算实例：求图中任意两点间的最短路。,解:(1)输入权矩阵 D(0)=D.,最短路问题,(2)计算 其中,计算,如：,其中,0,5,1,2,5,0,6,7,2,2 3 0 2 8,2 7 3 0 4,2 4 4 0,其中,表示从vi点到vj点,或直接有边或借v1点为中间点时的最短路长。,最短路问题,其中,表示从vi点到vj点,最多经中间点v1,v2的最短路长。,(2)计算 其中,计算,最短路问题,其中,表示从vi点到vj点,最多经中间点v1,v2,v3的最短路长。,(2)计算 其中,计算,最短路问题,其中,表示从vi点到vj点最多经中间点v1,v2,v3,v4,v5,计算,的所有路中的最短路长。,所以D(5)就给出了任意两点间不论几步到达的最短路长。,如果还希望给出具体的最短路经，则在运算过程中要保留下标信息，即 等等。,如在D(1)中的 是由,得到的，所以 可以写成.,而D(2)中的 是由,得到的，所以 可以写成.,最短路问题,而D(2)中的 是由,得到的，所以 可以写成.,而D(3)中的 是由,得到的，而 所以 可以写成 等.,最短路问题,由此,最短路问题,最短路问题的应用：电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。,v1（甲地）,15,17,6,2,4,4,3,10,6,5,v2,v7(乙地),v3,v4,v5,v6,最短路问题,例3,设备更新问题,某工厂使用一台设备，每年年初工厂都要作出决定如果继续使用旧的，要付维路费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。,若已知设备在各年年初的价格为：,还知使用不同年数的设备所需要的维修费用为：,例4,最短路问题,可供选则的设备更新方案是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为 5，五年合计为 25，于是五年总的支付费用为 59+25=84。,又如，决定在第一、三、五年各购进一台新设备，则其购置费用为11+12+13=36，维修费用为 5+6+5+6+5=27，于是五年总的支付费用为 36+27=63。,最短路问题,可把这个问题化为最短路问题。,用点vi表示第i年年初购进一台新设备虚设一个点v6,表示第五年年底。弧(vi,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底).,最短路问题,弧(vi,vj)上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用.例如(v1,v4):购置费11，维修费5+6+8=19，总计30.,最短路问题,这样设备更新问题就变为：求从v到v6 的最短路。求解得：v1,v3,v6 及 v1,v4,v6 均为最短路。总的支付费用均为53。,最短路问题,10.4 网络最大流,如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。,网络最大流,不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。,许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等.,网络最大流,管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如何充分利用装置的能力以取得最好效果(流量最大)，这类问题通常称为最大流问题。,50年代福持(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。,网络最大流,1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。,s,t,4,8,4,4,1,2,2,6,7,9,基本概念,网络最大流,2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。,3.流与可行流 流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。,容量限制条件。容量网络上所有的弧满足：0fijcij 中间点平衡条件。,若以v(f)表示网络中从st的流量，则有：,网络最大流,结论：任何网络上一定存在可行流。（零流即是可行流）,网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。,网络最大流,最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。,v(f)=7.,网络最大流,割与割集,割是指容量网络中的发点和收点分割开，并使st的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用 表示。,网络最大流,割集,网络最大流,网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。,网络最大流,如下图中，AA将网络上的点分割成 两个集合。并有，称弧的集合(v1,v3),(v2,v4)是一个割，且 的流量为18。,网络最大流,定理1 设网络N中一个从 s 到 t 的流 f 的流量为v(f)，(V,V)为任意一个割集，则 v(f)=f(V,V)f(V,V),推论1 对网络 N中任意流量v(f)和割集(V,V)，有v(f)c(V,V),证明 w=f(V,V)f(V,V)f(V,V)c(V,V),推论2 最大流量v(f)不大于最小割集的容量，即：v(f)minc(V,V),定理2 在网络中st的最大流量等于它的最小割集的容量，即：v(f)=c(V,V),网络最大流,增广链在网络的发点和收点之间能找到一条链，在该链上所有指向为st的弧，称为前向弧，记作+,存在f0，则称这样的链为增广链。,定理3 网络N中的流 f 是最大流当且仅当N中不包含任何增广链,网络最大流,一个可行流 f=fij，称 fij=cij 的弧为饱和弧，称 fij 0的弧为非零流弧.,饱和弧,网络最大流,设P是网络D的一条连接源点vs 和汇点vt 的链，定义链P的方向是从vs 到vt，前向弧弧的方向与P的方向一致；全体记为P+.后向弧弧的方向与P的方向相反；全体记为P-.,链P：,注：链不是有向路，链的每一边去掉方向是一条路.,则P中的弧可分为两类：,网络最大流,f 是一个可行流，P是从vs 到vt 的一条链，如果(1)P 的每一前向弧都是不饱和弧（）;(2)P 的每一后向弧都是非零流弧（）；则称 P 是网络 D 的关于可行流 f 的一条增广链。简称增广链。,增广链 P：,网络最大流,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(4),7(5),例如下图中，sv2v1v3v4t。,网络最大流,求网络最大流的标号算法：Ford-Fulkerson 算法基本思想 由一个流开始，系统地搜寻增广链，然后在此链上增流，继续这个增流过程，直至不存在增广链。,基本方法,找出第一个可行流，（例如所有弧的流量fij=0。）用标号的方法找一条增广链,首先给发点s标号(),标号中的数字表示允许的最大调整量。选择一个点 vi 已标号并且另一端未标号的弧沿着某条链向收点检查：,网络最大流,如果弧的起点为vi，并且有fij0，则vj标号(fji),(3)重复第(2)步，可能出现两种结局：,标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V,(V,V)为网络的最小割。t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步,网络最大流,(4)修改流量。设原图可行流为f，令,得到网络上一个新的可行流 f。,(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。,网络最大流,算例：求下面网络的最大流。,网络最大流,(1)给网络赋一个初始0流 f 0；给 vs 标号(-,);,(-,),(a)对弧(vi,vk),若,则给 vk 标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给 vk 标号(-vi,l(vk),其中,标号过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流 f 0 的增广链 P0=vs v1 v2 vt，,网络最大流,(-,),调整过程1,(+vs,8),(+vs,2),(+v1,5),(+v3,2),(+v2,5),找到流 f 0 的增广链 P0=vs v1 v2 vt，,2.调整流量,调整量,=5.,5,5,5,调整流值得流值为5的新可行流 f 1.,网络最大流,给 vs 标号(-,);,(-,),(a)对弧(vi,vk),若,则给 vk 标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给 vk 标号(-vi,l(vk),其中,标号过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流 f 1 的增广链 P1=vs v3 v2 vt，,得新可行流 f 1，,重新进入标号过程.,网络最大流,(-,),调整过程2,(+vs,3),(+vs,2),(+v3,2),(+v3,2),(+v2,2),找到流 f 1 的增广链 P1=vs v3 v2 vt，,2.调整流量,调整量,=2.,2,调整流值得流值为7的新可行流 f 2.,2,7,网络最大流,给 vs 标号(-,);,(-,),(a)对弧(vi,vk),若,则给 vk 标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给 vk 标号(-vi,l(vk),其中,标号过程3,(+vs,3),(+v1,3),(+v3,3),(+v3,3),(+v4,3),找到流 f 2 的增广链 P2=vs v1 v3 v4 vt，,得新可行流 f 2，,重新进入标号过程.,网络最大流,(-,),调整过程3,(+vs,3),(+v1,3),(+v3,3),(+v3,3),(+v4,3),找到流 f 2 的增广链 P2=vs v1 v3 v4 vt，,2.调整流量,调整量,=3.,8,调整流值得流值为10的新可行流 f 3.,3,3,3,网络最大流,给 vs 标号(-,);,(-,),(a)对弧(vi,vk),若,则给 vk 标号(+vi,l(vk),其中(b)对弧(vk,vi),若,则给 vk 标号(-vi,l(vk),其中,标号过程4,得新可行流 f 3，,重新进入标号过程.,标号无法进行,说明 f 3已是最大流，流值10.,网络最大流,用标号算法求下图中st的最大流量，并找出最小割。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),例5,网络最大流,解：(1)先给s标号(),s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),网络最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(2)检查与s点相邻的未标号的点，因fs1cs1，故对v1标号=min,cs1-fs1=1,(1),网络最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(6),(),(1),(2)检查与v1点相邻的未标号的点，因f13c13，故对v3标号=min1,c13-f13=min1,6=1,(1),网络最大流,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(4),7(5),(),(1),(1),(3)检查与v3点相邻的未标号的点，因f3tc3t，故对vt标号=min1,c3t-f3t=min1,1=1,(1),找到一条增广链sv1v3t,网络最大流,(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(7),9(3),5(4),10(8),6(1),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络最大流,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(0),2(0),9(9),5(3),7(5),(),(1),(1),(1),网络最大流,(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2)=min,2=2,(2),(1)=min2,3=2,(3)=min2,5=2,(2),(1),(4)=min2,1=1,(1),(t)=min1,2=1,网络最大流,(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,s,t,v1,v3,v2,v4,8(8),9(4),5(5),10(8),6(1),2(0),9(9),5(3),7(5),(),(2),(2),(2),(1),(1),网络最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(2),(2),(2),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,网络最大流,s,t,v1,v3,v2,v4,8(8),9(5),5(5),10(9),6(0),2(0),9(9),5(2),7(6),(),(1),(1),(1),(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。,(2)=min,1=1,(1)=min1,2=1,(3)=min1,4=1,网络最大流,求下图st的最大流，并找出最小割,网络最大流,例6,解:(1)在已知可行流的基础上，通过标号寻找增广链。,(),(2)=min,6=6,(6),(3)=min6,2=2,(2),(t)=min2,5=2,(2),存在增广链sv2v3 t,网络最大流,(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(6),(2),(2),网络最大流,(3)擦除原标号，重新搜寻增广链。,(),(6),(2),(2),网络最大流,(4)重新搜寻增广链。,(),(2)=min,4=4,(4),(1),(5)=min4,1=1,(3)=min1,2=1,(1),(1),(t)=min1,3=1,存在增广链：sv2v5v3 t,网络最大流,(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。,(),(4),(1),(1),(1),网络最大流,(6)擦除原标号,(),(4),(1),(1),(1),网络最大流,(),(1),(1),(1),(5)=min,1=1,(5)=min1,1=1,(5)=min1,2=1,(7)重新搜寻增广链。,存在增广链：sv5v3 t,网络最大流,(8)调整增广链上的流量，非增广链流量不变，得到新的可行流,(),(1),(1),(1),网络最大流,(),(1),(1),(1),(9)擦除原标号,网络最大流,(10)重新标号，搜索增广链,(),(1)=min,1=1,(1),(5)=min1,1=1,(1),(4)=min1,1=1,(1),(t)=min1,1=1,(1),存在增广链：sv1v5v4t,网络最大流,(),(1),(1),(1),(1),(11)调整增广链上的流量，非增广链流量不变，得到新的可行流,网络最大流,(),(1),(1),(1),(1),(11)擦除标号，在新的可行流上重新标号。,网络最大流,(),(11)擦除标号，在新的可行流上重新标号。,(3),(1)=min,3=1,无法标号，不存在增广链，此可行流已为最大流。最大流量为14。,网络最大流,10.5 最小费用最大流问题,最小费用最大流问题的数学模型,设网络D=(V,A,W)，每条弧(vi,vj)除了容量wij以外，,还给出单位流量的费用c(vi,vj)0，简记为cij。这样，,D就成为一个带费用的网络，记为D=(V,A,W,C)，其中，,C称为费用函数。,设X为D上的一个可行流，称,为可行流X的费用。,最小费用最大流问题,最小费用最大流问题，即要求一个最大流X，使总运输费用,达到最小值，则有最小费用最大流问题的数学模型,最小费用最大流问题,最小费用最大流问题的算法,寻求最大流的方法,最小费用,最小费用最大流,从某个可行流出发，找到关于这个可行流的一条增广链，沿着 该增广链调整X，对新的可行