运筹学第8-9章新

Chapter8图与网络分析

(GraphTheoryandNetworkAnalysis)图的基本概念与模型树与图的最小树最短路问题网络的最大流本章主要内容： 学习要点：

1.掌握一般图论及其基本概念；

2.能够应用最短路算法求解实际问题；

3.掌握最大流最小割理论。

18世纪，Königsberg是俄罗斯的一个城市（现为加里宁格勒）。市内有七座桥。人们在此散步，问：“能否从某处出发，经过每座桥一次且恰好一次又回到出发点？”1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答，发表了第一篇论文。七桥问题图的基本概念与模型中国邮路问题一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。问题：求一个圈，过每边至少一次，并使圈的长度最短。图的基本概念与模型Hamilton图游戏：用正十二面体上20个顶点表示20个城市，要求参加游戏者沿着各边行走，走遍每一个城市且仅走一次，最后回到出发城市。问题：如何判断一个图是否具有这样的性质。如果有，这样的行走路线如何确定。thedodecahedronisHamiltonian显然这样的路线存在且不唯一图的基本概念与模型50112463143726352362511225341538104964214013362761229523328391648760120415429594458533217426472574419305535854631564318在一个棋盘中，若马（马走日步）能否从某一点出发跳遍棋盘上每一点恰好一次，再回到出发点？对于4×4，5×5，或8×8的棋盘上马的跳动如何？图的基本概念与模型幻方问题图的基本概念与模型某团体举行舞会，其中有n个男士与n个女士，每个男士恰好认识r个女士，每个女士也恰好认识r个男士。问：在这个团中，能否做到：每个男士与其认识的女士跳舞，每个女士也与其认识的男士跳舞。比如：任意6个人，一定有3个人相互认识或者有3个人相互不认识鸽笼原理和Ramsey数图的基本概念与模型四色猜想

能否用四种颜色给地图染色，使相邻的国家有不同的颜色。问题：能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。图的基本概念与模型Möbius在1840年的一次演讲中提出如下问题：一个国王有五个儿子，要求在他死后将国土分成五部分，每个儿子占一部分并建立各自的宫殿。要求每座宫殿之间都有（平面的）路相连且互不相交（不允许立体交叉）。Tietze研究后指出这是不可能的。因为5个顶点的完全图不是平面图。平面图在印刷电路板中有重要的应用。平面图与网络图的基本概念与模型n-方体Qnn方体n维立方体n=3的情形，上底下底是两个2维立方体。对应顶点连线后(同时把上底中顶点标号末位加号0，下底中顶点标号末位加号1)得到3维立方体。完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连。完全二分图记为Km,nK3,3

K2,4

G2G1G2G1G2G1网络（赋权图）设图G＝（V，E），对G的每一条边(vi,vj)相应赋予数量指标wij，wij称为边(vi,vj)的权，赋予权的图G称为网络(或赋权图）。权可以代表距离、费用、通过能力(容量)等等。端点无序的赋权图称为无向网络，端点有序的赋权图称为有向网络。①②③④⑤⑥910201571419256图的基本概念与模型一个图是二部图当且仅当它不含奇圈。设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

其中：图的基本概念与模型v5v1v2v3v4v64332256437

下图所表示的图可以构造邻接矩阵A如下图的基本概念与模型例1v1v2v3v4v5v6v7v8v1v2v3v5v8v7e1e2e3e4e6e5e7e9e12e10e11e8v6v4

下图所表示的图可以构造邻接矩阵M如下:M=（mij）=101000000000110010000000010001110000000000001001001111000000000000001100000000000111000100110000图的基本概念与模型例2v5v1v2v3v4v64332256437

下图所表示的图可以构造权矩阵B如下:图的基本概念与模型例3树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。

乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员树与图的最小树

某企业的组织机构图也可用树图表示。树与图的最小树厂长人事科财务科总工程师生产副厂长经营副厂长技术科新产品开发科生产科设备科供应科动力科检验科销售科树是一个不包含圈的简单连通图。树中度为1的点称为树叶，度大于1的点称为分枝点。具有k个连通分支的不包含圈的图称为k-树，或森林。下是具有六个顶点的树，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。树：无圈的连通图即为树性质1：任何树中必存在次为1的点。性质2：n个顶点的树必有n-1条边。性质3：树中任意两个顶点之间，恰有且仅有一条链。性质4：树连通，但去掉任一条边，必变为不连通。性质5：树无回圈，但不相邻的两个点之间加一条边，恰得到一个圈。v1v2v3v4v5v6树与图的最小树图的最小部分树(支撑树)如果G2是G1的部分图，又是树图，则称G2是G1的部分树（或支撑树）。树图的各条边称为树枝。一般图G1含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（或最小支撑树）。v1v2v3v4v5v1v2v3v4v5G1G2树与图的最小树(赋权)图中求最小树的方法：破圈法和避圈法破圈法：任取一圈，去掉圈中最长边，直到无圈。5v1v2v3v4v5v6843752618v1v2v3v4v5v643521边数＝n-1=5树与图的最小树v1v2v3v4v5v643521得到最小树：MinC(T)=15树与图的最小树避圈法:

去掉G中所有边，得到n个孤立点；然后加边。加边的原则为：从最短边开始添加，加边的过程中不能形成圈，直到点点连通(即:n-1条边)。5v1v2v3v4v5v6843752618树与图的最小树v1v2v3v4v5v6435215v1v2v3v4v5v6843752618MinC(T)=15树与图的最小树8.3最短路问题如何用最短的线路将三部电话连起来？此问题可抽象为设△ABC为等边三角形，连接三顶点的路线（称为网络）。这种网络有许多个，其中最短路线者显然是二边之和（如AB∪AC）。ABC最短路问题ABCP但若增加一个周转站（新点P），连接4点的新网络的最短路线为PA＋PB＋PC。最短新路径之长比原来只连三点的最短路径要短。这样得到的网络不仅比原来节省材料，而且稳定性也更好。最短路问题问题描述： 就是从给定的网络图中找出一点到各点或任意两点之间距离最短的一条路。

有些问题，如选址、管道铺设时的选线、设备更新、投资、某些整数规划和动态规划的问题，也可以归结为求最短路的问题。因此这类问题在生产实际中得到广泛应用。最短路问题

渡河游戏 一老汉带了一只狼、一只羊、一棵白菜想要从南岸过河到北岸，河上只有一条独木舟，每次除了人以外，只能带一样东西；另外，如果人不在，狼就要吃羊，羊就要吃白菜，问应该怎样安排渡河，才能做到既把所有东西都运过河去，并且在河上来回次数最少？这个问题就可以用求最短路方法解决。最短路问题例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

的最短路问题。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的最短路。v1v2v3v4v5最短路问题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

的最短路.0--∞-∞PT-∞-∞-∞-∞开始，给vs以P标号，P(vs)=0,其余各点给T标号T(vi)=+∞.227414731555vsv2v1vtv4v5v3Step1:

迭代1

Dijkstra算法基本步骤：例2最短路问题0--∞-∞-∞-∞-∞-∞若vi为刚得到

P标号的点,考虑这样的点

vj

:(vi,vj)∈E

且vj

为

T标号。227414731555vsv2v1vtv4v5v3Step2:对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标号，227414731555vsv2v1vtv4v5v3Step3:245即

P(vi)=min[T(vi)].当存在两个以上最小者时,可同时改为P

标号。若全部点为P标号,则停止。否则用vi代替vi转step2.-2迭代1

全部T标号中,T(v1)最小,令P(v1)=2,记录路径(vs

,v1).最短路问题0-2--5-∞-∞-∞-4227414731555vsv2v1vtv4v5v394若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--4-9-∞-∞-4227414731555vsv2v1vtv4v5v344迭代2

比较所有具有T标号的点，把最小者改为P标号，Step3:即

P(vi)=min[T(vi)].--全部T标号中,T(v2),T(v3)最小,令P(v2)=4,P(v3)=4,记录路径(v1,v2),(v1,v4),.最短路问题0-2-4--9-∞-∞4-227414731555vsv2v1vtv4v5v37迭代3

若vi为刚得到

P标号的点,考虑这样的点

vj

:(vi,vj)∈E且vj

为

T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路问题0-2-4--9-∞-74-227414731555vsv2v1vtv4v5v37迭代3

比较所有具有T标号的点，把最小者改为P标号，Step3:即

P(vi)=min[T(vi)].-最短路问题0-2-4--9-∞7-4-227414731555vsv2v1vtv4v5v3迭代4

若vi为刚得到

P标号的点,考虑这样的点

vj

:(vi,vj)∈E且vj

为

T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]814最短路问题0-2-4--8-147-4-227414731555vsv2v1vtv4v5v3迭代4

8-比较所有具有T标号的点，把最小者改为P标号，Step3:即

P(vi)=min[T(vi)].最短路问题0-2-4-8--147-4-227414731555vsv2v1vtv4v5v3迭代5

13若vi为刚得到

P标号的点,考虑这样的点

vj

:(vi,vj)∈E且vj

为

T标号。Step2:对vj的T标号进行如下更改T(vj)=min[T(vj),P(vi)+wij]最短路问题0-2-4-8--137-4-227414731555vsv2v1vtv4v5v3迭代5

13比较所有具有T标号的点，把最小者改为P标号，Step3:即

P(vi)=min[T(vi)].当存在两个以上最小者时,可同时改为P

标号。若全部点为P标号,则停止。否则用vi代替vi转step2.-最短路问题0-2-4-8-13-7-4-227414731555vsv2v1vtv4v5v3最短路

Dijkstra算法不仅找到了所求最短路，而且找到了从vs

点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。最短路问题从上例知，只要某点已标号，说明已找到起点vs到该点的最短路线及最短距离，因此可以将每个点标号，求出vs到任意点的最短路线，如果某个点vj不能标号，说明vs不可达vj

。最短路问题算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。v2vsv15-58最短路问题例2Ford算法基本思想：为逐次逼近的方法。每次求出从出发点v0到其余点的有限制的最短路，逐次放宽条件。即第一次逼近是找v0到vn的最短路，但限于最短路只允许有一条边（弧），其距离记为d1(v0,vn).简记为d1(vn)。第二次逼近，再找v0到vn的最短路，其限制条件放宽到允许最短路不超过两条边（弧），其距离记为d2(vn)。到第m次逼近,dm(vn)表示由v0到vn的不超过m条边（弧）组成的最短路的距离。最多p-1次。网络有负权的最短路最短路问题2-2-2311v0v2v1v3Ford算法基本步骤：(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-2-2311v0v2v1v3(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).最短路问题2-2-2311v0v2v1v3解：③

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).最短路问题2-2-2311v0v2v1v3最后解得：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算法其中最短路问题权矩阵：v1v2v4v3v55122310284462图中有四条无向边，每条均可化为两条方向相反的有向边。则得权矩阵为：最短路问题(1)输入权矩阵D(0)=D;(2)计算其中(3)中元素Floyd算法基本步骤：就是vi到vj的最短路长.最短路问题计算实例：求图中任意两点间的最短路。解:(1)输入权矩阵D(0)=D.v1v2v4v3v55122310284462最短路问题(2)计算其中计算如：其中0512∞506722302827304∞2440v1v2v4v3v55122310284462其中表示从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)中的是由得到的，而所以可以写成等.最短路问题由此v1v2v4v3v55122310284462最短路问题最短路问题的应用：电信公司准备准备在甲、乙两地沿路架设一条光缆线，问如何架设使其光缆线路最短？下图给出了甲乙两地间的交通图。权数表示两地间公路的长度（单位：公里）。

v1（甲地）1517624431065v2v7(乙地)v3v4v5v6最短路问题例3设备更新问题某工厂使用一台设备，每年年初工厂都要作出决定．如果继续使用旧的，要付维路费；若购买一台新设备，要付购买费。试制定一个5年的更新计划，使总支出最少。若已知设备在各年年初的价格为：还知使用不同年数的设备所需要的维修费用为：例4年度第1年第2年第3年第4年第5年购买费1111121213使用年数0-11-22-33-44-5维修费用5681118最短路问题可供选则的设备更新方案是很多的。例如，每年都购置一台新设备，则其购置费用为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年年底).v1v2v3v4v5v6最短路问题弧(vi,vj)上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买、维修的全部费用.例如(v1

,v4):购置费11，维修费5+6+8=19，总计30.v1v2v3v4v5v6161617171830412322312359413022年度第1年第2年第3年第4年第5年购买费1111121213使用年数0-11-22-33-44-5维修费用5681118最短路问题这样设备更新问题就变为：求从v１到v6的最短路。求解得：{v1

,v3

,

v6

}及{v1

,v4

,

v6

}均为最短路。总的支付费用均为53。v1v2v3v4v5v6161617171830412322312359413022最短路问题8.4网络最大流如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。网络最大流不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等.8528796653vsv1vtv4v3v2网络最大流管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如何充分利用装置的能力．以取得最好效果(流量最大)，这类问题通常称为最大流问题。50年代福持(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。8528796653vsv1vtv4v3v2网络最大流

1.容量网络：队网络上的每条弧(vi,vj)都给出一个最大的通过能力，称为该弧的容量，简记为cij。容量网络中通常规定一个发点(也称源点，记为s)和一个收点(也称汇点，记为t)，网络中其他点称为中间点。s①②③④t4844122679基本概念网络最大流2.网络的最大流

是指网络中从发点到收点之间允许通过的最大流量。3.

流与可行流流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。满足以下条件的一组流称为可行流。容量限制条件。容量网络上所有的弧满足：0≤fij≤cij

中间点平衡条件。若以v(f)表示网络中从s→t的流量，则有：网络最大流结论：任何网络上一定存在可行流。（零流即是可行流）网络最大流问题： 指满足容量限制条件和中间点平衡的条件下，使v(f)值达到最大。网络最大流最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2v(f)=7.网络最大流割与割集割是指容量网络中的发点和收点分割开，并使s→t的流中断的一组弧的集合。割容量是组成割集合中的各条弧的容量之和，用表示。网络最大流(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2割集网络最大流网络的割集有多个，其中割集容量最小者称为网络的最小割集容量(简称最小割)。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2网络最大流如下图中，AA′将网络上的点分割成两个集合。并有，称弧的集合{(v1,v3),(v2,v4)}是一个割，且的流量为18。●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(3)7(6)AA’BB’网络最大流定理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的弧，称为前向弧，记作μ+,存在f<c；所有指向为t→s的弧，称为后向弧，记做μ－，若f>0，则称这样的链为增广链。定理3

网络N中的流f

是最大流当且仅当N中不包含任何增广链网络最大流一个可行流f={fij}，称fij=

cij的弧为饱和弧，称fij<cij的弧为不饱和弧.

fij=

0的弧为零流弧，fij>

0的弧为非零流弧.(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2饱和弧零流弧不饱和弧网络最大流设P是网络D的一条连接源点vs和汇点vt的链，定义链P的方向是从vs到vt

，前向弧—弧的方向与P的方向一致；全体记为P

+.后向弧—弧的方向与P的方向相反；全体记为P

-.链P：(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2注：链不是有向路，链的每一边去掉方向是一条路.则P中的弧可分为两类：网络最大流f

是一个可行流，P是从vs到vt的一条链，如果(1)P的每一前向弧都是不饱和弧（）;(2)P的每一后向弧都是非零流弧（）；则称P是网络D的关于可行流f

的一条增广链。简称增广链。(5,8)(4,5)(2,2)(3,8)(1,7)(6,9)(1,6)(2,6)(0,5)(0,3)vsv1vtv4v3v2增广链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，并且有fij<Cij，则给vj标号为(Cij－fij)

如果弧的方向指向vi，并且有fji>0，则vj标号(fji)(3)重复第(2)步，可能出现两种结局：标号过程中断，t无法标号，说明网络中不存在增广链，目前流量为最大流。同时可以确定最小割集，记已标号的点集为V,未标号的点集合为V′,(V,V′)为网络的最小割。

t得到标号，反向追踪在网络中找到一条从s到t得由标号点及相应的弧连接而成的增广链。继续第(4)步网络最大流(4)修改流量。设原图可行流为f，令得到网络上一个新的可行流f′。(5)擦除图上所有标号，重复(1)-(4)步，直到图中找不到任何增广链，计算结束。网络最大流8528796653vsv1vtv4v3v2算例：求下面网络的最大流。网络最大流(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(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，网络最大流(0,8)(0,5)(0,2)(0,8)(0,7)(0,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(-,∞)调整过程1(+vs,8)(+vs,2)(+v1,5)(+v3,2)(+v2,5)找到流f0

的增广链P0=vsv1v2vt，2.调整流量调整量θ=5.555调整流值得流值为5的新可行流f1.网络最大流(5,8)(5,5)(0,2)(0,8)(0,7)(5,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2给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

，重新进入标号过程.网络最大流(5,8)(5,5)(0,2)(0,8)(0,7)(5,9)(0,6)(0,6)(0,5)(0,3)vsv1vtv4v3v2(-,∞)调整过程2(+vs,3)(+vs,2)(+v3,2)(+v3,2)(+v2,2)找到流f1

的增广链P1=vsv3v2vt，2.调整流量调整量θ=2.2调整流值得流值为7的新可行流f2.27网络最大流(5,8)(5,5)(2,2)(0,8)(0,7)(7,9)(0,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2给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

，重新进入标号过程.网络最大流(5,8)(5,5)(2,2)(0,8)(0,7)(7,9)(0,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2(-,∞)调整过程3(+vs,3)(+v1,3)(+v3,3)(+v3,3)(+v4,3)找到流f2

的增广链P2=vsv1v3v4vt，2.调整流量调整量θ=3.8调整流值得流值为10的新可行流f3.333网络最大流(8,8)(5,5)(2,2)(3,8)(3,7)(7,9)(3,6)(0,6)(2,5)(0,3)vsv1vtv4v3v2给vs标号(-,∞);(-,∞)(a)对弧(vi,vk),若,则给vk

标号(+vi,l(vk)),其中(b)对弧(vk,vi),若,则给vk

标号(-vi,l(vk)),其中标号过程4得新可行流f3

，重新进入标号过程.标号无法进行,说明f3已是最大流，流值10.令S={vs},则(S,S)是最小割.网络最大流用标号算法求下图中s→t的最大流量，并找出最小割。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)例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<cs1，故对v1标号=min{∞,cs1-fs1}=1,(1)网络最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(6)(∞)(1)(2)检查与v1点相邻的未标号的点，因f13<c13，故对v3标号=min{1,c13-f13}=min{1,6}=1(1)网络最大流●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(4)7(5)(∞)(1)(1)(3)检查与v3点相邻的未标号的点，因f3t<c3t，故对vt标号=min{1,c3t-f3t}=min{1,1}=1(1)找到一条增广链s→v1→v3→t网络最大流(4)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。●stv1v3v2v48(7)9(3)5(4)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)网络最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。●stv1v3v2v48(8)9(4)5(5)10(8)6(0)2(0)9(9)5(3)7(5)(∞)(1)(1)(1)网络最大流(5)擦除所有标号，重复上述标号过程，寻找另外的增广链。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)ε(2)=min{∞,2}=2(2)ε(1)=min{2,3}=2ε(3)=min{2,5}=2(2)(1)ε(4)=min{2,1}=1(1)ε(t)=min{1,2}=1网络最大流(6)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。●stv1v3v2v48(8)9(4)5(5)10(8)6(1)2(0)9(9)5(3)7(5)(∞)(2)(2)(2)(1)(1)网络最大流●stv1v3v2v48(8)9(5)5(5)10(9)6(0)2(0)9(9)5(2)7(6)(∞)(2)(2)(2)(1)(1)(7)擦除所有标号，重复上述标号过程，寻找另外的增广链。网络最大流●stv1v3v2v48(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)=min{1,2}=1ε(3)=min{1,4}=1网络最大流例6.9求下图s→t的最大流，并找出最小割stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●网络最大流stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●解:(1)在已知可行流的基础上，通过标号寻找增广链。(∞)ε(2)=min{∞,6}=6(6)ε(3)=min{6,2}=2(2)ε(t)=min{2,5}=2(2)存在增广链s→v2→v3→t网络最大流(2)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(4)3(2)1(1)4(3)3(2)5(3)4(2)2(2)7(6)8(3)●(∞)(6)(2)(2)网络最大流(3)擦除原标号，重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(6)(2)(2)网络最大流(4)重新搜寻增广链。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)ε(2)=min{∞,4}=4(4)(1)ε(5)=min{4,1}=1ε(3)=min{1,2}=1(1)(1)ε(t)=min{1,3}=1存在增广链：s→v2→v5→v3→t网络最大流(5)修改增广链上的流量，非增广链上的流量不变，得到新的可行流。stv1v2v3v4v54(3)3(2)10(6)3(2)1(1)4(3)3(2)5(3)4(4)2(2)7(6)8(5)●(∞)(4)(1)(1)(1)网络最大流(6)擦除原标号stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(4)(1)(1)(1)网络最大流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)ε(5)=min{∞,1}=1ε(5)=min{1,1}=1ε(5)=min{1,2}=1(7)重新搜寻增广链。存在增广链：s→v5→v3→t网络最大流(8)调整增广链上的流量，非增广链流量不变，得到新的可行流stv1v2v3v4v54(3)3(2)10(7)3(2)1(1)4(3)3(3)5(4)4(4)2(2)7(6)8(6)●(∞)(1)(1)(1)网络最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(9)擦除原标号网络最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(10)重新标号，搜索增广链(∞)ε(1)=min{∞,1}=1(1)ε(5)=min{1,1}=1(1)ε(4)=min{1,1}=1(1)ε(t)=min{1,1}=1(1)存在增广链：s→v1→v5→v4→t网络最大流stv1v2v3v4v54(3)3(3)10(7)3(2)1(1)4(3)3(3)5(5)4(4)2(2)7(6)8(7)●(∞)(1)(1)(1)(1)(11)调整增广链上的流量，非增广链流量不变，得到新的可行流网络最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(1)(1)(1)(1)(11)擦除标号，在新的可行流上重新标号。网络最大流stv1v2v3v4v54(4)3(3)10(7)3(3)1(1)4(4)3(3)5(5)4(4)2(2)7(7)8(7)●(∞)(11)擦除标号，在新的可行流上重新标号。(3)ε(1)=min{∞,3}=1无法标号，不存在增广链，此可行流已为最大流。最大流量为14。网络最大流第9章网络计划1网络计划图2时间参数计算3网络计划的优化用网络分析的方法编制的计划称为网络计划技术,

是20世纪50年代末发展起来的一种编制大型工程进度计划的有效方法。网络计划是运用工程网络图来表达计划的内容及其相互之间的关系，通过分析、计算找到整个计划的主要矛盾、关键环节，然后进行调整，以求得完工日期、技术资源及成本的优化方案。主要内容有关键路线法(criticalpathmethod,缩写为CPM)，计划评审方法(programevaluation&reviewtechnique，缩写为PERT)等．我国已故著名数学家华罗庚先生将这些方法总结概括称为统筹方法．在60年代初引入我国．而且身体力行地进行推广应用。目前，这些方法被世界各国广泛应用于工业、农业、国防、科研等计划管理中，对缩短工期、节约人力、物力和财力，提高经济效益发挥了重要作用.在制定企业不同业务部门的系统规划时，制定网络计划，并找出在编制计划时及计划执行过程中的关键路线的方法，称为关键路线法(CPM).计划评审方法(PERT)侧重于用网络分析与网络计划的方法对各项工作安排的评价和审查等．编制网络计划包括绘制网络图，计算时间参数，确定关键路线及网络优化等环节。基本术语及绘制网络图规则网络图是由结点、弧及权所构成的有向图。弧表示一个工序，结点表示一个事项。工序：为了完成工程项目，在工程技术和组织管理上相对独立的工作或活动(消耗时间或资源)．用a

表示.(一)网络图9.1、网络计划图事项：工序的开始或结束为事项，是相邻工序在时间上的分界点。用有标号的结点i表示。工程的开始事项称为最初事项，标号为①，工程的结束事项为最终事项，标号为n.权：一个工序所消耗的时间、资源等数据为权。通常标注在弧的下方或其他合适的位置上。12467835abcfdgekhl60101820253035404515例：如图就是一项研制新产品工程的网络图。箭尾事项、箭头事项.(二)、画图注意事项：(1)、网络图只能有一个开始事项，一个结束事项.方向：整个图的方向遵循从左向右的原则；编号：同一工序箭尾事项的编号小于箭头事项的编号．12345678cabdefg(2)、两事项间只有一个工序5ijcba3(3)、不允许回路123(4)、紧前工序与紧后工序12467835abcfdgekhl60101820253035404515a为b,c,d,e的紧前工序；b,c,d,e

为a的紧后工序.必须正确表示工序间的紧前、紧后关系如4道工序a,b,c,d的关系为：c必须在a,b均完成后才能开工，而d只要在b完工后即可开工，如画成下图是错误的，因本来与a工序无关的工序d被错误地表为必须在a完成后才能开工。12435acbd(5)、虚工序②正确表达工序的紧前、紧后关系①解决画法中问题为了表达相邻工序之间的衔接关系，而虚设的工序，称为虚工序。不消耗资源。ij0③

表达平行作业④

表达交叉作业00012346578cabedfg①解决画法中问题0ijkc5a3b5ijcba30例1、a,b,c,d四个工序，c在a,b完工后开始，d在b完工后开始。cabdabcd②正确表达工序的紧前、紧后关系例2、已知ABCEADC例2、答案ABDCE③

表达平行作业abc12acb344b2b14一道工作分为几道工作同时进行，称为平行工作.④

表达交叉作业ab96a1a2a3b1b2b3a