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

Chapter10图与网络分析(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流学习要点：1.掌握一般图论及其基本概念；2.能够应用最短路算法求解实际问题；3.掌握最大流最小割理论。18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 了第一篇论文。七桥问题图的基本概念与模型中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一图的基本概念与模型在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的棋盘上马的跳动如何？图的基本概念与模型50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318幻方问题图的基本概念与模型某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识鸽笼原理和Ramsey数图的基本概念与模型四色猜想能否用四种颜色给地图染色，使相邻的国家有不同的颜色。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。图的基本概念与模型Möbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。平面图与网络图的基本概念与模型n-方体Qnn方体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，集X∪Y=V,X∩Y=Ø,使得同一集合中任意两个顶点均不相邻，称这样的图为偶图。(a)(b)(c)(a)明显为二部图，(b)也是二部图，但不明显，改画为(c)时可以清楚看出。图的基本概念与模型完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,nK3,3K2,4G2G1G2G1G2G1网络（赋权图）设图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可得：图的基本概念与模型图的矩阵描述：如何在计算机中存储一个图呢？现在已有很多存储的方法，但最基本的方法就是采用矩阵来表示一个图，图的矩阵表示也根据所关心的问题不同而有：邻接矩阵、关联矩阵、权矩阵等1.邻接矩阵对于图G=（V，E），|V|=n，|E|=m，有nn阶方矩阵A=(aij)nn，其中图的基本概念与模型2.关联矩阵对于图G=(V,E),|V|=n,|E|=m,有mn阶矩阵M=(mij)mn，其中:3.权矩阵图的基本概念与模型下图所表示的图可以构造邻接矩阵A如下图的基本概念与模型v1v2v3v4v5v6v7v8下图所表示的图可以构造邻接矩阵M如下:M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000图的基本概念与模型下图所表示的图可以构造权矩阵B如下:图的基本概念与模型树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。运动员树与图的最小树某企业的组织机构图也可用树图表示。树与图的最小树树是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点。具有k个连通分支的不包含圈的图称为k-树，或森林。下是具有六个顶点的树，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。树与图的最小树图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝。一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。G1G2树与图的最小树(赋权)图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。v1v2v3v4v5v643521边数＝n-1=5树与图的最小树得到最小树：MinC(T)=15树与图的最小树避圈法:去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。树与图的最小树v1v2v3v4v5v643521MinC(T)=15树与图的最小树10.3最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题问题描述：就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题渡河游戏一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路问题定义：1）人—M（Man），狼—W（Wolf），羊—G（Goat），草—H（Hay）2）点——vi表示河岸的状态3）边——ek表示由状态vi经一次渡河到状态vj4）权——边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的最短路问题。v1v2v3v4v5u5u4u3u2u1最短路问题求最短路有两种算法:狄克斯屈拉(Dijkstra)标号算法逐次逼近算法最短路问题狄克斯屈拉(Dijkstra)标号算法的基本思路：若序列{vs，v1…..vn-1，vn}是从vs到vt间的最短路，则序列{vs，v1…..vn-1}必为从vs到vn-1的最短路。假定v1→v2→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的标号;1.令起点的标号；b(s)＝0。最短路问题求连接vs、vt的最短路.开始，给vs以P标号，P(vs)=0,其余各点给T标号T(vi)=+∞.Step1:迭代1Dijkstra算法基本步骤：最短路问题-∞-∞PT-∞-∞-∞-∞若vi为刚得到P标号的点,考虑这样的点vj:(vi,vj)∈E且vj为T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]245迭代1考察vs,T(v2)=min[T(v2),P(vs)+ws2]=min[+∞,0+5]=5T(v1)=min[T(v1),P(vs)+ws1]=min[+∞,0+2]=2最短路问题0--∞-∞-∞-∞-∞-∞比较所有具有T标号的点，把最小者改为P标号，Step3:245即P(vi)=min[T(vi)].当存在两个以上最小者时,可同时改为P标号。若全部点为P标号,则停止。否则用vi代替vi转step2.-2迭代1全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs,v1).最短路问题0--∞-∞-∞-∞-∞-∞94若vi为刚得到P标号的点,考虑这样的点vj:(vi,vj)∈E且vj为T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]迭代2考察v1,T(v4)=min[T(v4),P(v1)+w14]=min[+∞,2+7]=9T(v2)=min[T(v2),P(v1)+w12]=min[5,2+2]=4最短路问题0-2--5-∞-∞-∞-444迭代2比较所有具有T标号的点，把最小者改为P标号，Step3:即P(vi)=min[T(vi)].--全部T标号中,T(v2),T(v3)最小,令P(v2)=4,P(v3)=4,记录路径(v1,v2),(v1,v4),.最短路问题2--4-9-∞-∞-47迭代3若vi为刚得到P标号的点,考虑这样的点vj:(vi,vj)∈E且vj为T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路问题2-4--9-∞-∞4-7迭代3比较所有具有T标号的点，把最小者改为P标号，Step3:即P(vi)=min[T(vi)].-最短路问题2-4--9-∞-74-迭代4若vi为刚得到P标号的点,考虑这样的点vj:(vi,vj)∈E且vj为T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]814最短路问题2-4--9-∞7-4-迭代48-比较所有具有T标号的点，把最小者改为P标号，Step3:即P(vi)=min[T(vi)].最短路问题2-4--8-147-4-迭代513若vi为刚得到P标号的点,考虑这样的点vj:(vi,vj)∈E且vj为T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路问题2-4-8--147-4-迭代513比较所有具有T标号的点，把最小者改为P标号，Step3:即P(vi)=min[T(vi)].当存在两个以上最小者时,可同时改为P标号。若全部点为P标号,则停止。否则用vi代替vi转step2.-最短路问题2-4-8--137-4-最短路Dijkstra算法不仅找到了所求最短路，而且找到了从vs点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。最短路问题2-4-8-13-7-4-从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj。最短路问题算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。v2vsv15-58最短路问题Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找v0到vn的最短路，但限于最短路只允许有一条边（弧），其距离记为d1(v0,vn).简记为d1(vn)。第二次逼近，再找v0到vn的最短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为d2(vn)。到第m次逼近,dm(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.021-2第一次逼近最短路问题(2)令解：②d2(v1)=min{d1(v1)+w(v1,v1),d1(v2)+w(v2,v1),d1(v3)+w(v3,v1)}021-2当vi,v为同一个点时，有w(v,vi)=0.=min{2+0,1+∞,-2+3}=1.1d2(v2)=min{d1(v1)+w(v1,v2),d1(v2)+w(v2,v2),d1(v3)+w(v3,v2)}=min{2-2,1+0,-2+∞}=0.0d2(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)}010-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.-1d3(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.01-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)计算其中计算如：其中0512∞506722302827304∞2440其中表示从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（甲地）1517624431065v2v7(乙地)v3v4v5v6最短路问题设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定．如果继续使用旧的，要付维路费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。若已知设备在各年年初的价格为：还知使用不同年数的设备所需要的维修费用为：最短路问题年度第1年第2年第3年第4年第5年购买费1111121213使用年数0-11-22-33-44-5维修费用5681118可供选则的设备更新 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 是很多的。例如，每年都购置一台新设备，则其购置费用为11+11+12+12+13=59，而每年支付的维修费用为5，五年合计为25，于是五年总的支付费用为59+25=84。又如，决定在第一、三、五年各购进一台新设备，则其购置费用为11+12+13=36，维修费用为5+6+5+6+5=27，于是五年总的支付费用为36+27=63。最短路问题年度第1年第2年第3年第4年第5年购买费1111121213使用年数0-11-22-33-44-5维修费用5681118可把这个问题化为最短路问题。用点vi表示第i年年初购进一台新设备．虚设一个点v6,表示第五年年底。弧(vi,vj)表示第i年初购进的设备一直使用到第j年年初(即第j-1年年底).最短路问题弧(vi,vj)上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用.例如(v1,v4):购置费11，维修费5+6+8=19，总计30.最短路问题年度第1年第2年第3年第4年第5年购买费1111121213使用年数0-11-22-33-44-5维修费用5681118这样设备更新问题就变为：求从v１到v6的最短路。求解得：{v1,v3,v6}及{v1,v4,v6}均为最短路。总的支付费用均为53。最短路问题10.4网络最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。网络最大流不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等.网络最大流管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如何充分利用装置的能力．以取得最好效果(流量最大)，这类问题通常称为最大流问题。50年代福持(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。网络最大流1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常 规定 关于下班后关闭电源的规定党章中关于入党时间的规定公务员考核规定下载规定办法文件下载宁波关于闷顶的规定 一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t4844122679基本概念网络最大流2.网络的最大流是指网络中从发点到收点之间允许通过的最大流量。3.流与可行流流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。容量限制条件。容量网络上所有的弧满足：0≤fij≤cij中间点平衡条件。若以v(f)表示网络中从s→t的流量，则有：网络最大流结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题：指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。网络最大流最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。v(f)=7.网络最大流割与割集网络最大流割集网络最大流网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。网络最大流网络最大流定理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)min{c(V,V´)}定理2在网络中s→t的最大流量等于它的最小割集的容量，即：v＊(f)=c＊(V,V´)网络最大流增广链在网络的发点和收点之间能找到一条链，在该链上所有指向为s→t的弧，称为前向弧，记作μ+,存在f0，则称这样的链为增广链。定理3网络N中的流f是最大流当且仅当N中不包含任何增广链网络最大流一个可行流f={fij}，称fij=cij的弧为饱和弧，称fij0的弧为非零流弧.饱和弧网络最大流设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：网络最大流●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(4)7(5)例如下图中，s→v2→v1→v3→v4→t。网络最大流求网络最大流的标号算法：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流f0；给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)找到流f0的增广链P0=vsv1v2vt，网络最大流(-,∞)调整过程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0的增广链P0=vsv1v2vt，2.调整流量调整量θ=5.555调整流值得流值为5的新可行流f1.网络最大流给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)找到流f1的增广链P1=vsv3v2vt，得新可行流f1，重新进入标号过程.网络最大流(-,∞)调整过程2(+vs,3)(+vs,2)(+v3,2)(+v3,2)(+v2,2)找到流f1的增广链P1=vsv3v2vt，2.调整流量调整量θ=2.2调整流值得流值为7的新可行流f2.27网络最大流给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)找到流f2的增广链P2=vsv1v3v4vt，得新可行流f2，重新进入标号过程.网络最大流(-,∞)调整过程3(+vs,3)(+v1,3)(+v3,3)(+v3,3)(+v4,3)找到流f2的增广链P2=vsv1v3v4vt，2.调整流量调整量θ=3.8调整流值得流值为10的新可行流f3.333网络最大流给vs标号(-,∞);(-,∞)(a)对弧(vi,vk),若,则给vk标号(+vi,l(vk)),其中(b)对弧(vk,vi),若,则给vk标号(-vi,l(vk)),其中标号过程4得新可行流f3，重新进入标号过程.标号无法进行,说明f3已是最大流，流值10.网络最大流用标号算法求下图中s→t的最大流量，并找出最小割。stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)网络最大流解：(1)先给s标号(∞)stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)网络最大流stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)(2)检查与s点相邻的未标号的点，因fs1