运筹学第7章图与网络优化

Chapter7图与网络优化图的基本概念与模型树最短路问题网络最大流问题最小费用最大流问题中国邮递员问题本章主要内容：1

图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学,控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。引言2

1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。欧拉将这个问题抽象成一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。

欧拉在他的论文中证明了这是不可能的。因为这个图形中每一个顶点都与奇数条边相连，不可能将它一笔画出，这就是古典图论中的第一个著名问题。ABCD

七桥问题3

一邮递员送信，要走完他所负责的全部街道分送信件，最后返回邮局。邮递员都会本能地以尽可能少的行程完成送信任务。如何走路线最短。1962年，由我国数学家管梅谷提出，国际上称为中国邮递员问题。中国邮递员问题，即

求一个圈，过每边至少一次，并使圈的长度最短。

中国邮递员问题4

四色猜想

能否用四种颜色给地图染色，使相邻的国家有不同的颜色。

能否用四种颜色给平面图的点染色，使有公共边的点有不同的颜色。5第一节图的基本概念6在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。例1.

左图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线图等等。连云港武汉南京徐州上海北京塘沽青岛济南天津郑州7例2有甲、乙、丙、丁、戊五支球队，它们之间的比赛情况也可以用图表示。设点v1,v2,v3,v4,v5分别代表甲、乙、丙、丁、戊五支球队。若两支球队之间比赛过，则在相应的点之间联一条线，且这条线不过其他点。如下图所示：v1v2v3v4v5可知各队之间的比赛情况如下：甲——乙、丙、丁、戊乙——甲、丙丙——甲、乙、丁丁——甲、丙、戊戊——甲、丁8例3储存8种化学药品，其中某些药品不能存放在同一个库房里。用v1,v2,…,v8分别代表这8种药品。规定若两种药品不能存放在一起，则其相应的点之间联一条线。如下图所示：v1v2v3v4v5v6v7v8可知需要4个库房，其中一个答案是：{v1

}{v2,v4,v7

}{v3,v5}{v6,v8}还有其他的答案。9由以上例子可见：图是反映实际生活中某些对象之间关系的一种工具。通常用点代表研究的对象，用点与点之间的连线表示这两个对象之间有特定的关系。在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显的并不重要。如反映例2中球队之间的比赛情况的下述两种图没有本质上的区别。10v3v1v2v4v6v5

例1-例3中涉及到的对象之间的“关系”具有“对称性”。即：如果甲与乙有某种关系，则乙与甲也有同样的这种关系。然而实际生活中，有许多关系不具有这种对称性。如例2中的比赛胜负情况就不能用简单的连线来表示。为了反映这种关系，可以用一条带箭头的连线表示。例4有六支球队进行足球比赛，我们分别用点v1…v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。11基本概念点：研究对象（车站、国家、球队）；点间连线：对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果)。对称关系：桥、道路；用不带箭头的连线表示，称为边。非对称关系：甲队胜乙队，用带箭头的连线表示，称为弧。图：点及边（或弧）组成。对称关系非对称关系12有向图

由点及弧所构成的图，记为D=(V,A)，V,A分别是D的点集合和弧集合。无向图由点及边所构成的图。记为G=(V,E),

V，E分别是G的点集合和边集合。v1v2v3v4v1v2v3v4a1a2a3a4a5e1e2e3e4e5a6e6连接点vi,vjV的边,记作

[vi,vj]或[vj,vi]。一条方向从vi指向vj的弧，记作

(vi,vj)。13例如.图8-4是一个无向图G=（V，E）其中V={v1,v2,v3,v4}

E={[v1,v2],[v2,v1],[v2,v3],[v3,v4],[v1,v4],[v2,v4],[v3,v3]}v3v2v1v4图8-414图8-5是一个有向图D=（V，A）其中V={v1,v2,v3,v4,v5,v6,v7}A={(v1,v2),(v1,v3),(v3,v2),(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)}v7v5v3v4v2v1v6图8-515v3e7e4e8e5e6e1e2e3v1v2v4v5端点,关联边,相邻若边e可表示为e=[vi,vj]，称vi和vj是边e的端点，称边e为点vi或vj的关联边。若点vi，vj与同一条边关联，称点vi和vj相邻；若边ei和ej具有公共的端点，称边ei和ej相邻。在一个图的几何实现中，两条边的交点可能不是图的顶点。例如图G中的点数记为p(G)，边数记为q(G).简记为p，q.此时，图G可以表示为G=(p,q).16

环

若在图G中，某个边的两个端点相同，则称e是环。如e7v1v2v3v4e1e2e3e4e5e6e7

多重边

若两个点之间有多于一条的边，称这些边为多重边。如

e1,e2

简单图

一个无环，无多重边的图。

多重图

一个无环、但允许有多重边的图。环,多重边,简单图注：无特别声明我们今后讨论的图都是简单图.17

点v的次

以点vi为端点边的个数，记为dG(vi)或d(vi)。注：环在计算次时算做两次v1v2v3v4e1e2e3e4e5e6e7如d(v4)=5d(v2)=4v5

悬挂点

次为1的点，如

v5

悬挂边

悬挂点的关联边，如

e8e8

孤立点

次为0的点

偶点

次为偶数的点，如

v2

奇点

次为奇数的点,如

v5

次，奇点，偶点，孤立点18

链：

由两两相邻的点及其相关联的边构成的点边序列,如:

（v0,e1,v1,e2,v2,e3,v3,…,vn-1,en,vn

）;其中v0，vn分别为链的起点和终点，v1,v2,…,vn-1称为中间点；

圈：起点与终点重合的链；

简单链（圈）：链（圈）中所含的边均不相同；

初等链（圈）：链（圈）中所含的点均不相同,也称通路；

链，圈，初等链，初等圈，简单链（圈）19

链中间点初等链圈初等圈简单圈

v1v2v5v6v7v3v4e1e2e4e3e5e6e7e8e9在上图中,(v1,v2,v3,v4,v5,v3,v6,v7)是一条简单链,但不是初等链在该链中,v2,v3,v4,v5,v3,v6是中间点(v1,v2,v3,v6,v7)是一条初等链(v1,v2,v3,v4,v1)是一个初等圈(v4,v1,v2,v3,v5,v7,v6,v3,v4)是一个简单圈20

连通图图G中，若任何两个点之间，至少有一条链，称为连通图。否则称为不连通图。

连通分图(分图)若G是不连通图，则它的每个连通的部分称为连通分图。v1v2v3v4e1e2e3e4e5e6v5v6e7如左图就是个不连通图，它是由两个连通分图构成的。

连通图、子图、支撑子图、基础图21给定图G=（V，E），若图G’=（V’，E’），其中V’V，E’E

，则称G’是G的子图。给定图G=（V，E），若图G’=（V，E’），其中E’E，则称G’是G的一个支撑子图（部分图）。点全部保留（a）（b）子图（c）部分图子图与部分图（支撑子图）22e1e3e2Gv3v4v5v2v1G-{v1,v5}e1e3e2v3v4v5v2v1顶点导出子图：

设W是图G的一个非空顶点子集,从G中删除W中顶点以及与这些顶点相关联的边所得到的子图称为导出子图，记为G-W23

基础图给定一个有向图D=(V,A)，从D中去掉所有弧上的箭头，所得到的无向图称为基础图。记之为G(D)。v1v2v3v4a1a2a3a4a5a6D=(V,A)v1v2v3v4e1e2e3e4e5e6G(D)24有向图：关联边有方向弧：有向图的边a=(u,v),起点u,终点v;路：若有从u到v不考虑方向的链,且各方向一致,则称之为从u到v的路；初等路:

各顶点都不相同的路；

初等回路:u=v的初等路;

连通图：

若不考虑方向是无向连通图;

强连通图：任两点有路;

有向图、弧、路、初等路25v1v2v3v4a1a2a3a4a5a6a7a8a9a10a11v6v7

路初等路回路v526图的基本性质：定理1任何图中，顶点次数之和等于所有边数的2倍。定理2任何图中，奇点的个数必为偶数个。证明：由于每条边必与两个顶点关联，在计算点的次时，每条边均被计算了两次，所以顶点次数之和等于边数的2倍。证明：设V1和V2分别为图G中奇点与偶点的集合。由定理1可得：2m为偶数，且偶点的次之和也为偶数，所以必为偶数，即奇数点的个数必为偶数。27第二节树树的概念构造生成树的方法最小生成树问题本节主要内容：28树是图论中结构最简单但又十分重要的图。在自然和社会领域应用极为广泛。乒乓求单打比赛抽签后，可用图来表示相遇情况，如下图所示。ABCDEFGH运动员29某企业的组织机构图也可用树图表示。厂长人事科财务科总工程师生产副厂长经营副厂长技术科新产品开发科生产科设备科供应科动力科检验科销售科302.1树的定义及性质证明树的定义：一个无圈的连通图称为树。定理3设图G=(V,E)是一个树，p(G)≥2，则G中至少有两个悬挂点。31定理4图G=(V,E)是一个树的充分必要条件是G中不含圈，且恰有p-1条边(即：q(G)=p(G)-1)。证明充分性：只需证明G为连通的即可。32

定理5图G=(V,E)是一个树的充分必要条件是G是连通图，并且q(G)=p(G)-1。首先，G存在悬挂点。否则，因为G连通并且，所以对于任意点vi，都有。从而证明：由定理4，必要性显然。充分性：只需证明G不含圈即可。数学归纳法：p(G)=1,2时，结论显然成立。假设p(G)=n时，结论成立。下证p(G)=n+1时结论成立。设vi为G的一个悬挂点。则G-vi仍为连通图，并且由归纳假设：G-vi不含圈。所以G不含圈。33定理6图G是树的充分必要条件是任意两个顶点之间恰有一条链。证明：由树的定义，必要性显然。充分性：因为任两个顶点间恰有一条链，显然G是连通的。如果G中含有圈的话，则其中至少有两个顶点间有两条链，这与题设矛盾。所以G是树，充分性得证。推论：

从一个树中去掉一条边，则余下的图是不连通的。由此知，在点集合相同的所有图中，树是含边数最少的连通图。在树中不相邻的两个点间添上一条边，则恰好得到一个圈。进一步地说，如果再从这个圈上任意去掉一条边，可以得到一个树。342.2图的支撑树定义：设图T=(V,E’)是图G的支撑子图，如果图T=(V,E’)是一个树，则称T是G的一个支撑树。

定理：图G有支撑树的充要条件是图G是连通的。证明：必要性显然。充分性：设G是连通的。分两种情形。若G不含圈，则G本身是一个树，从而G是它自身的一个支撑树。若G含圈，任取一个圈，从圈中任意地去掉一条边，得到图G的一个支撑子图G1。如果G1不含圈，那么G1是G的一个支撑树；如果G1仍含圈，那么从G1中任取一个圈，从圈中再任意去掉一条边，得到图G的一个支撑子图G2，如此重复，最终可以得到G的一个支撑子图Gk,它不含圈，于是Gk是G的一个支撑树。35支撑树的求解方法

破圈法：任取一个圈，从圈中去掉一个边，对剩余的图重复上述步骤，直到没有圈为止。例用破圈法求解图的一个支撑树v1v2v3v4v5e1e2e3e4e5e6e7e8这就得到了该图的一个支撑树。36v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9这就得到了该图的一个支撑树。

避圈法：在图中任取一条边，找一条与不构成圈的边，再找一条与不构成圈的边。一般，设已有，找一条与中的任何一条边不构成圈的边。重复上述过程，直到不能进行为止。

372.3最小支撑树问题定义3给图G=(V,E)，若G中的每一条边[vi,vj]，相应地有一个数wij，则称这样的图G为赋权图，wij称为边[vi,vj]上的权。定义4如果T=(V,E’)是G的一个支撑树，称E’中所有边的权之和为支撑树T的权，记为w(T)，即最小支撑树如果支撑树T*的权w(T*)是G的所有支撑树的权中最小者，则称T*是G的最小支撑树(简称最小树),即38最小支撑树的求法方法一避圈法

开始选一条权最小的边，以后每一步中，总从未被选取的边中选一条权最小的边，并使之与已选取的边不构成圈。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。39方法二破圈法

任取一个圈，从圈中去掉一条权最大的边。在余下的图中，重复这个步骤，一直到一个不含圈的图为止，这时的图便是最小树。v1v2v3v4v5v6651572344这就得到了该图的一个最小支撑树。4077ABCDEST2254143515练习：用破圈法求解41第三节最短路问题42一、最短路问题的提出v1v2v3v4v5v6v7v8v9132216610410423236例左图为单行线交通网，弧旁数字表示通过这条单行线所需要的费用。求从v1出发到v8总费用最小的路线。有很多条路线可供选择。每条路线的费用就是相应的路中各条弧的费用之和。如上图所示的路线为最短路线。43在图论中，最短路问题可归结为以下几步：(1)给定一个赋权有向图D＝(V,A)及w(a)=

wij；(2)给定D中两个顶点vs、vt，P是D中从vs到vt的一条路；(3)定义路P的权:

P中所有弧的权之和，即w(P)＝wij

；(4)求一条权最小的路P0:

w(P0)=minw(P)上式中对D中所有从vs到vt的路P取最小，称P0是从vs到vt的最短路。路P0的权称为从vs到vt的距离，记为d(vs，vt)。

显然，d(vs，vt)与d(vt，vs)不一定相等。44最短路问题的特性：若序列{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若求起点A到任一点G的最短路线，可先求A到G点的相邻前点的最短距离，在此基础上求出A到G点的最短距离。这样最终一定能求出起点到终点的最短距离。45基本思想：从始点vs出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。执行过程中，与每个点对应，记录下一个数(称为这个点的标号)

1.标号P（固定标号或永久性标号）

从始点vs到该标号点vj的最短路权记为P(vj)

。2.标号T（临时性标号）

从始点vs到该标号点vj的最短路权上界记为T(vj)该方法的每一步就是去修改T标号，并且把某一个具T标号的点改变为具有P标号的点，从而使D中具P标号的顶点数多一个，至多经过n-1步，就可以求出始点vs到各点的最短路。最短路问题求解方法-Dijkstra算法3.前点标号m

：

表示始点vs到vj的最短路上vj的前一点是vm。m

,P(vj)m,T(vj)vm,T(vj)vm

,P(vj)46Dijkstra算法步骤：

第二步：修改T标号。假定vi是新产生的P标号点，考察以vi为始点的所有弧段（vi，vj）。如果vj是P标号点，则对vj点不再进行标号；如果vj是T标号点，则将vj的T标号修改为T(vj)=min[T(vj),P(vi)+wij]其中，方括号内的T(vj)代表vj点旧的T标号值；方括号外的T(vj)代表vj点新的T标号值。第三步：产生新的P标号点。其原则如下：在现有的T标号中将值最小者改为P标号。重复以上步骤，直至终点的T标号改为P标号为止。第一步：始点标上固定标号P(vs)=0,其余各点标临时性标号

T(vj)=,j1;

47图上标号法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞M,∞M,∞M,∞永久标号永久标号临时标号v1出发到v8去，使总费用最小的旅行路线j

,P(vj)j,T(vj)M,

∞M,∞M,∞48v1,6图上标号法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,

∞v1,3M,∞M,∞M,∞v1,1v1,1永久标号永久标号临时标号v1出发到v8去，使总费用最小的旅行路线j

,P(vj)j,T(vj)49v1,6图上标号法v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞M,∞v1,3M,∞M,∞M,∞0,0v1,1v4,11v1,3永久标号临时标号v1出发到v8去，使总费用最小的旅行路线j

,P(vj)j,T(vj)50v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v1,1M,∞M,∞M,∞1,3图上标号法v4,11v1,3v1,6v3,5v3,5永久标号临时标号v1出发到v8去，使总费用最小的旅行路线j,T(vj)j

,P(vj)51v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞M,∞v1,3图上标号法v3,5v2,6v2,6永久标号临时标号v1出发到v8去，使总费用最小的旅行路线j,T(vj)j

,P(vj)52v5v223464v3v1v41210

61210v8v9v72363v60,0M,∞v4,11v1,1M,∞M,∞v1,3v5,12v5,9v5,9图上标号法v3,5v2,6永久标号临时标号v5,10v1出发到v8去，使总费用最小的旅行路线j,T(vj)j

,P(vj)53v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v5,12v1,3v5,9v5,12v3,5v2,6图上标号法永久标号临时标号v5,10v1出发到v8去，使总费用最小的旅行路线j,T(vj)j

,P(vj)54v5v223464v3v1v41210

61210v8v9v72363v60,0v5,10v1,1M,∞v1,3v5,12v3,5v2,6图上标号法v5,9永久标号临时标号标号结束反向追踪v1出发到v8去，使总费用最小的旅行路线j,T(vj)j

,P(vj)55算法适用条件：Dijkstra算法只适用于全部权为非负情况，如果某边上权为负的，算法失效。此时可采用逐次逼近算法。如右图所示中按dijkstra算法可得P(v1)=5为从vs→v1的最短路长显然是错误的，从vs→v2→v1路长只有3。v2vsv15-58例256wij不全0Dijkstra算法失效，即虽然完整的路线比完整中的片断距离短，但也不能断定该完整路线一定最短。只能采用最原始的思想，即找出vs到vj

的所有路线的权，才能确定vs到vj

的最短距离。具体算法如下：设有向图中有n个点，从vi

到vj的最短路线不一定从vi直达vj，也可能经过一个、两个或n－2个中间点才能到达vj

。把vi直达vj，称为走一步，经过一个中间点称为走二步，则vi到vj的最短路线最多走n－1步。57582-2-2311v0v2v1v3例求下图所示赋权有向图中从v1到各点的最短路。592-2-2311v0v2v1v3基本步骤：(1)令t=1,令d1(v0，v0)=0,d1(v0，vi)=w(v0,vi).解：①

d1(v0，v0)=0,d1(v0，v1)=2,d1(v0，v2)=1,d1(v0，v3)=-2.021-2第一次逼近602-2-2311v0v2v1v3(2)令解：②

d2(v0，v1)=min{d1(v0，v1)+w(v1,v1),d1(v0，v2)+w(v2,v1),

d1(v0,v3)+w(v3,v1)}=min{2+0,1+∞,-2+3}=1.021-2当vi,vj为同一个点时，有w(vi

,vj)=0.1d2(v0，v2)=min{d1(v0,v1)+w(v1,v2),d1(v0,v2)+w(v2,v2),d1(v0,v3)+w(v3,v2)}=min{2-2,1+0,-2+∞}=0.0d2(v0,v3)=min{d1(v0,v1)+w(v1,v3),d1(v0,v2)+w(v2,v3),d1(v0,v3)+w(v3,v3)}=min{2+∞,1+1,-2+0}=-2.第二次逼近(3)若t+1=p则停止。否则t=t+1,转(2).612-2-2311v0v2v1v3解：③

d3(v0，v1)=min{d2(v0，v1)+w(v1,v1),d2(v0，v2)+w(v2,v1),d2(v0，v3)+w(v3,v1)}=min{1+0,0+∞,-2+3}=1.010-2d3(v0，v2)=min{d2(v0，v1)+w(v1,v2),d2(v0，v2)+w(v2,v2),

d2(v0，v3)+w(v3,v2)}=min{1+(-2),1+0,-2+∞}=-1-1d3(v0，v3)=min{d2(v0，v1)+w(v1,v3),d2(v0，v2)+w(v2,v3),d2(v0，v3)+w(v3,v3)}=min{1+∞,0+1,-2+0}=-2.第三次逼近(2)令当vi,vj为同一个点时，有w(vi

,vj)=0.(3)若t+1=p则停止。否则t=t+1,转(2).622-2-2311v0v2v1v3最后解得：d3(v0,v1)=1，d3(v0,v2)=-1，d3(v0,v3)=-2.01-1-2即v0到v1最短路长度为d3(v0,v1)=1，最短路为v0,v3,v1.即v0到v2最短路长度为d3(v0,v2)=-1,最短路为v0,v3,v1,v2.即v0到v3最短路长度为d3(v0,v3)=-2,最短路为v0,v3.63v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57例:求v1到图中其他各点的最短路。64v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)走1步时65v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-1)(v1,3)(v1,-2)(v1,)(v1,)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,5)(v4,11)(v4,5)(v2,1)走2步时66v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v1,)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,1)(v6,0)(v4,5)(v4,-5)(v6,6)走3步时(v5,0)(v2,1)(v4,1)(v2,-3)(v6,0)(v7,4)67v1v2v3v4v5v6v7v86-1-283-3-5-121112-1-3-57(v1,0)(v1,-2)(v6,6)(v1,)(v3,-5)(v3,-7)(v3,-1)(v2,-3)(v6,0)(v4,-5)走4步时(v5,-4)(v2,1)(v4,1)(v6,0)(v7,-6)(v8,3)(v8,1)68wijd(t)(vi,vj)

v1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v48023-7-7-7v5-101-3-3v61017-1-1-1v7-105-5-5v8-3-5066说明：表中空格处为+。缺点：不能解决负回路的情况。69第四节网络最大流70如何制定一个运输计划使生产地到销售地的产品输送量最大。这就是一个网络最大流问题。71不同网络中流的意义不同，流本身是一种输送，可以把它们统称为运输网络的流。许多系统包含了流量问题。例如在交通运输网络中有人流、车流、货物流；供水网络中有水流；金融系统中有现金流；通讯系统中有信息流，等等.8528796653vsv1vtv4v3v272管道网络中每边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题就是要讨论如何充分利用装置的能力．以取得最好效果(流量最大)，这类问题通常称为最大流问题。50年代福持(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。8528796653vsv1vtv4v3v273s①②③④t4844122679定义设赋权有向图D=(V,A),在V中指定一个发点vs和一个收点vt

,其他的点叫做中间点。对于D中的每一个弧(vi,vj)∈A,都有一个权cij

叫做弧的容量。我们把这样的图D叫做一个网络系统，简称网络，记做D=（V，A，C）。4.1基本概念与基本定理74v3v2v1v4vs（2）（3）（2）（5）（3）（3）（6）（1）（1）（2）fij上图表示了网络上的一个流（运输方案）弧上的流量fij就是运输量例如fs1=5,fs2=3,f13=2等等。vt流是指加在网络各条弧上的实际流量，对加在弧(vi,vj)上的负载量记为fij。若fij=0，称为零流。75网络系统上流的特点：发点的总流出量和收点的总流入量必相等；每一个中间点的流入量与流出量的代数和等于零；每一个弧上的流量不能超过它的最大通过能力（即容量）。76定义7满足下述条件的流f称为可行流：(1)容量限制条件：对每一弧(vi,vj)∈A

（2）平衡条件：对于中间点：流入量等于流出量，即对于每个i(i≠s,t)，有对于发点vs

，记对于收点vs，记式中v(f)称为这个可行流的流量，即发点的净输出量（或收点的净输入量）。77

v(f)最大的可行流f称为最大流，记为f*。可用以下LP模型求解。对于任何网络，其可行流f一定存在。如令fij=0，f为可行流，其v(f)=0。78给定一个可行流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饱和弧零流弧不饱和弧零流弧和饱和弧79设P是网络中的一条连接源点vs和汇点vt的链，定义链P的方向是从vs到vt，则P中的弧可分为两类：

前向弧—弧的方向与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前向弧和后向弧80设f是一可行流，是从vs到vt的一条链，若满足下列条件，则称之为（关于流f的）一条增广链：在弧(vi,vj)+上，0fij<cij(非饱和弧)（即前向弧是非饱和弧）在弧(vi,vj)‐上，0<fijcij

(非零流弧)（后向弧是非零流弧）定义8增广链vsv2v1v3v4vt10(5)8(3)4(1)5(2)3(2)6(3)3(3)11(6)17(2)5(1)在左图中,(vs,v1,v2,v3,v4,vt)是一条增广链,因为+和‐中的弧满足增广链的条件。如：81可扩充量调整后的弧流量

由于增广链上的前向弧都是非饱和弧，反向弧都是非零流弧，所以沿着这条增广链可以继续增加流量，其增量为82vsv2v1v3v4vt432115234截集与截量截集:83(8,5)(5,4)(2,2)(8,3)(7,1)(9,6)(6,1)(6,2)(5,0)(3,0)vsv1vtv4v3v2截集V184截量

显然，若把截集去掉，则从vs到vt的路将不存在。截量制约了从vs到vt的流量。(8,5)(5,4)(2,2)(8,3)(7,1)(9,6)(6,1)(6,2)(5,0)(3,0)vsv1vtv4v3v2V185定理8可行流f*是最大流的充要条件是不存在关于f*的增广链证明：由截集的定义可知：

截集是从vs到vt的必经之路，无论去掉哪个截集，vs到vt都不存在路。因此任何一个可行流的流量不会超过任何一个截集的容量。显然，若能找到一个可行流和一个截集，使得可行流的流量等于这个截集的容量，则该可行流一定是最大流，该截集一定是最小截集。

86下证充分性：87求解网络最大流的基本原理基本思路：

根据增广链上可以增加流量的特点。对于网络中的一个可行流来说，如果存在一条从始点vs到终点vt的增广链，那么根据增广链的定义，可以从vs到vt增加一定的流量。这样就得到了一个新的可行流。对新的可行流，再找出增广链继续增加流量。重复以上步骤，直到网络中不存在增广链为止。这时网络中的可行流就是最大流。88求网络最大流的标号法通过逐点进行标号的方法来寻求从始点到终点的一条增广链，然后根据这条增广链上可能增加的流量大小来调整网络中的流量。1.标号过程：从起点开始，沿存在增广链的方向对邻近的未标号顶点进行标号。每个标号共分为两部分：第一个标号表明增广链的源头，即说明到该顶点的增广链是从哪一个顶点过来的；第二个标号表示到该顶点为止的增广链可以增加流量的大小。如果标号过程一直可以进行到终点，则表明从始点到终点存在一条增广链，然后转入流量调整过程；89在标号过程中，从任一顶点vi出发都要确定标号的可增加流量。根据增广链的定义，有下面两种情况：从已标号的顶点vi出发的弧是正向弧，则当fij<cij时，顶点vj可以标号。沿着增广链到顶点vj为止可能增加的流量值受到两个限制：1)到前一个顶点vi为止可能增加的流量值(vi)，2)在新增加的弧段上允许的增加值(cij-fij)。

从而，顶点vj为止的增广链可以增加的流量为

(vj)=min

[(vi),cij-fij]从已标号的顶点vi出发的弧是反向弧，则当fji>0时，顶点vj可以标号。为了标明是从反向弧过来的，第一个标号记为负。vj处可增加的流量为：

(vj)=min[(vi),fji]902.调整过程

在标号过程进行到终点vt之后，从终点开始，根据第一个标号逆向追踪找出增广链，然后根据在此增广链上可能增加的流量值(vt)调整流量，具体调整办法如下：在增广链的正向弧上增加流量(vt)；在反向弧上减去流量(vt)。调整结果得到网络的一个新可行流，再对此新可行流重复上面的标号和流量调整过程。如果从网络图中任一已标号点出发不存在满足上面两种情况的弧段，则标号过程停止。当这种标号过程不能进行到终点时，说明从起点到终点不存在增广链。这时，网络中的可行流就是最大流。91例：求下图中网络的最大流，图中弧上的数字代表(fij,cij)vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)92第一次迭代：(vj)=min[(vi),cij-fij]vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞]0表示始点∞表示无流量增加的上限93vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞](v1)=min[(vs),cs1-fs1]=min[∞,5-2]=3[+vs,3]94vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,3]f13=c13f21=095vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞]

(v2)=min[(vs),cs2-fs2]=min[∞,4-0]=4[+vs,4][+vs,3]96vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,4][+vs,3]f21<c21,(v1)=min[(v2),c21-f21]=min[4,1-0]=1f31=0,→[+v2,1]f24<c24,(v1)=min[(v2),c21-f21]=min[4,4-0]=4[+v2,4]97vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)[0,∞][+vs,4][+vs,3]f4t<c4t,(vt)=min[(v4),c4t-f4t]=min[4,5-2]=3→[+v2,1][+v2,4][+v4,3]至此，终点vt已经被标号，即已经找到一条从始点到终点的增广链，转入调节流量过程。98vsv2v4v1v3v5vt(0,4)(2,5)(0,1)(0,4)(2,5)(2,3)(0,1)(2,2)(0,4)(0,2)从终点反向追踪找到增广链为vs→v2→v4→vt。在这条增广链上增加流量(vt)=3，得到如下图的当前流f(1):(3,4)(3,4)(5,5)[+vs,4][+v2,4][+v4,3][0,∞]99vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)第二次迭代：对下图所示的当前流f(1)寻找增广链[+vs,1][0,∞][+vs,3]100vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)对于正向弧(v1，v3)，f13=c13，故划去对于反向弧(v2，v1)，f21=0，故划去[+vs,1][0,∞][+vs,3]101vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)[+vs,1][0,∞][+vs,3]对于正向弧(v2，

v4),(v4)=min[(v2),c24-f24]=min[1,4-3]=1对于反向弧(v3，

v2),f32=0，故划去对于正向弧(v2，

v1),也可以标号，但由于至v1无法再进行下去，故中止[+v2,1]→[+v2,1]102vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)对于正向弧(v4，

vt),f4t=c4t，故划去对于反向弧(v3，

v4),(v3)=min[(v4),f34]=min[1,2]=1[+vs,1][0,∞][+vs,3][+v2,1][-v4,1]103vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)对于正向弧(v3，

v5)

(v5)=min[(v3),c34-f35]=min[1,4-0]=1[+vs,1][0,∞][+vs,3][+v2,1][-v4,1][+v3,1]104vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(2,3)(0,1)(2,2)(0,4)(0,2)对于正向弧(v5，

vt)

(vt)=min[(v5),c5t-f5t]=min[1,4-0]=1对vt进行标号，从而得到一条从始点到终点的增广链。[+vs,1][0,∞][+vs,3][+v2,1][-v4,1][+v3,1][+v5,1]105vsv2v4v1v3v5vt(3,4)(2,5)(0,1)(3,4)(5,5)(0,1)(2,2)(0,4)(0,2)从终点反向追踪找到增广链为：vs→v2→v4→v3→v5→vt。增广链上增加流量(vt)=1，得到如下图的当前流f(2):(4,4)(4,4)(2,3)(1,4)(1,2)(1,3)[+vs,1][0,∞][+v2,1][-v4,1][+v3,1][+v5,1]106vsv2v4v1v3v5vt(4,4)(2,5)(0,1)(4,4)(5,5)(0,1)(2,2)(1,4)(1,2)对当前流f(2)，标号过程在点vs和点v1因(vs,v2),(v1v3)两条弧是饱和弧，而(v2，v1)是无流量的反向弧而中止。即对当前流f(2)来说，不再存在增广链，算法停止，当前流f(2)就是最大流。(1,3)[+vs,3]107第五节最小费用最大流问题108一.基本概念1.什么是最小费用最大流问题？

对每一条弧都给出单位流量费用的容量网络D=(V,A,C)(称为费用容量网络)，求取最大流f，使输送流量的总费用b(f)=∑bijfij

为最小的一类优化问题。其中，cij表示弧(vi,vj)上的容量，bij表示弧(vi,vj)上通过单位流量所花费的费用，fij表示弧(vi,vj)上的流量。vivj(cij,bij,fij)2.最小费用流对于一个费用容量网络，具有相同流量v(f)的可行流中，总费用b(f)最小的可行流称为该费用容量网络关于流量v(f)的最小费用流，简称流量为v(f)的最小费用流。109②增广链μ的费用定义为：以单位调整量调整可行流时所付出的费用；即：当修正量ε=1时，注：

①

f’的流量v(f’)=v(f)+1；3.增广链的费用

当沿着一条关于可行流f的增广链（流量修正路线）μ，以修正量ε=1进行调整，得到新的可行流f’，则称b(f’)-b(f)为增广链μ的费用。110（1）定理若f是流量为v(f)的最小费用流，μ是关于f的所有增广链中费用最小的增广链，那么沿着μ去调整f得到的新的可行流就是流量为的最小费用流。二.求解最小费用最大流问题的方法1.求解途径

始终保持网络中的可行流是最小费用流，然后不断调整，使流量逐步增大，最终成为最小费用的最大流；2.算法原理111（2）实现思路基于求解途径，根据上述定理，从流量为v(f)的最小费用流f开始，只要找到其上的最小费用增广链，在该链上调整流量，就得到增加流量后的最小费用流。循环往复就可以求出最小费用最大流。

实施中的关键——寻找最小费用增广链具体方法：构造增广费用网络图，借助最短路算法寻找最小费用增广链。112增广费用网络图的构造方法

将流量网络中的每一条弧（vi,vj）都看作一对方向相反的弧，并定义弧的权数如下：

vivj(cij,fij)wij

=bij若fij<cij+∞若fij=cijwji

=-bij若fij>0+∞若fij=0113零流弧上(fij=0)，保持原弧不变，将单位费用作为权数，即wij=bij:vibijvivj-bij饱和弧上(fij=cij)：去掉原有弧，添加以单位费用的负数作为权数后向弧（虚线弧）：

非饱和且非零流弧上(cij>fij>0)，原有弧以单位费用作权数，并添加以单位费用的负数作为权数后向弧（虚线弧）ViVjbij-bijvjwij

=bij

若fij<cij+∞若fij=cijwji

=-bij

若fij>0+∞若fij=0114第一步

取初始可行流为零流

，它必为流量等于0的最小费用流。

第二步对该可行流f(0)构造增广费用网络图W(f(0))，用最短路算法求出从发点到收点的最短路(寻找f(0)的最小费用增广链)。若不存在最短路，则该可行流即为最小费用最大流，停止迭代；否则，转下一步。

第三步将最短路还原成流量网络图（cij,fij）中的最小费用增广链μ，在μ上对可行流f(0)进行调整(采用最大流问题中的增广链流量调整方法)，得到新的可行流图返回第二步，将f(0)替换为新的可行流即可。

3.整个过程的求解步骤：115例求下图的最小费用最大流，弧旁的数字为(cij,bij)。vsvtv2v3v1(10,4)(7,1)(8,1)(10,3)(4,2)(5,2)(2,6)解：（1）以零流弧为初始可行流f(0)，则初始可行流的流量v(f(0))=0。116vsvtv2v3v14113226(5,

0)(7,

0)vsvtv2v3v1(10,0)(8,

0)(10,

0)(4,

0)(2,

0)第1次迭代①f(0)中全部是零流弧,则保持原边不变,单位费用为权；②所有的权均大于零，可用D氏标号法求出最短路：即是f(0)的最小费用增广链。

①流量调整量ε1=min{8-0,5-0,7-0}=5总流量v(f(1))=5②最小费用增广链的费用∑bij=1+2+1=4③新的可行流为f(1),总费用b1=4×5=20

(8,5)(5,5)(7,5)117第2次迭代1v1vt-2

6v2v34-132

1vs-1(7,

5)vsvtv2v3v1(10,

0)(8,

5)(10,

0)(4,

0)(2,

0)(5,

5)①零流弧保持原边,非饱和非零流弧(vs,v2)和(v1,vt)增添后向弧,饱和弧(v2,v1)去掉原弧增添后向弧；②用列表法求出最短路:即是f(1)的最小费用增广链。①流量调整量ε2=min{10-0,7-5}=2，总流量v(f(2))=原流量+新增流量=5+2=7；②最小费用增广链的费用∑bij=4+1=5③新的可行流为f(2),总费用b2=原费用+新增费用=20+5×2=30(10,2)(7,7)118vsvtv2v3v14-4-1-132

6-21①零流弧保持原边，非饱和非零流弧增添后向弧，饱和弧去掉原边增添后向弧②用列表法求得最短路即是f(2)的最小费用增广链。①流量调整量ε3=min{8-5,10-0,4-0}=3，总流量v(f(3))

=原流量+新增流量=7+3=10；②最小费用增广链的费用∑bij=1+3+2=6③新的可行流为f(3),总费用b3=原费用+新增费用=30+6×3=48第3次迭代(7,

7)vsvtv2v3v1(10,

2)(8,

5)(10,

0)(4,

0)(2,

0)(5,

5)(8,8)(10,3)(4,3)119

634vsvtv2v3v1-3-1-1-22-4

-2①添加弧；②用列表法求得最短路

③对应最小费用增广链①调整流量ε4=min{10-2,5,10-3,4-3}=1，总流量v(f(4))

=10+1=11；②最小费用增广链的费用∑bij=4-2+3+2=7③新的可行流为f(4),总费用b4=原费用+新增费用

=48+7×1=55。第4次

迭

代(7,

7)vsvtv2v3v1(10,

2)(8,

8)(10,

3)(4,

3)(2,

0)(5,

5)(10,3)(5,4)(10,4)(4,4)120

634vsvtv2v3v1-3-1-1-2-4

-2①添加弧；②用列表法计算发现Vs和Vt之间不存在一条最短路，计算结束。当前的可行流f(4)即为所求的最小费用最大流。第5次

迭

代2121总结最短路算法与最大流算法的结合运用

1）构造初始可行流的增广费用网络，用最短路算法求出最小费用增广链。2）将最小费用增广链还原到容量流量网络图中的增广链，调整流量得到新的可行流，继续进行，直到用最短路算法找不到最小费用增广链。122第六节中国邮递员问题123一、问题的提出用图的语言描述