运筹学胡运权第08章

1、(Graph Theory and Network Analysis)|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题环球旅行问题环球旅行问题一个图是由点集V=vj和V中元素的无序对的一个集合E=ek构成的二元组，记为G =(V,E),其中V 中的元素vj 叫做顶点，V表示图G的点集合；E中的元素ek 叫做边，E 表示图 G 的边集合。v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例 654321,vvvvvvV ,10987654321eeeeeeeeeeE， ,211vve ,212vve

2、 ,323vve ,434vve ,315vve ,536vve ,537vve ,658vve ,669vve ,6110vve 图图1 1定义定义1 1如果一个图是由点和边所构成的，则称其为无向图，记作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) , (v

3、2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) 图图2一条边的两个端点是相同的,那么称为这条边是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。每一对顶点间都有边相连的无向简单图称为完全图。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义定义2 2定义定义3 3定义定义4 4图G=(V,E)的点集V可以分为两个非空子集X，Y，即XY=V,XY=，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y

4、，则称G为二部图(偶图)，有时记作G=(X,Y,E)。X:v1, v3, v5Y:v2, v4, v6v1v3v5v6v4v2v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的关联边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。以点v为端点的边的个数称为点v 的度（次），记作 。)(vd图中d(v1)= 4，d(v6)= 4（环计两度）定义定义5 5有向图中，以vi为始点的边数称为点vi的出次，用 表示；以vi为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。所有顶点的入次之和等于所有顶

5、点的出次之和。)(ivd )(ivd 定理定理1 1定理定理2 2所有顶点度数之和等于所有边数的2倍。在任一图中，奇点的个数必为偶数。定义定义6 6图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在实际应用中，给定一个图G=（V,E）或有向图D=（V,A）,在V中指

6、定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点。对每一条弧 ，对应一个数 ，称为弧上的“权”。通常把这种赋权的图称为网络。 Avvji ),(j iw定义定义8 8无向图G=(V,E)，若图G中某些点与边的交替序列可以排成(vi0,ei1,vi1,ei2,vik-1,eik,vik)的形式，且eit=(vit-1,vit)(t=1,k)，则称这个点边序列为连接vi0与vik的一条链，链长为k。点边列中没有重复的点和重复边者为初等链。无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中既无重复点也无重复边者为

7、初等圈。定义定义9 9定义定义1010一个图中任意两点间至少有一条链相连，则称此图为连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图。对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同。对于网络（赋权图）G=（V,E）, ,其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵。),(jivvjiw EvvEvvwajijijiji),(0),(nnjiaA )(设图G=（V,E）中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵。 nnj

8、iaA )( EvvEvvajijiji),(0),(1定义定义1111定义定义1212当G为无向图时，邻接矩阵为对称矩阵。654321654321 010101101001010111101010001101111010vvvvvvvvvvvvB 例例权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437654321654321 030303302004020576305020007204346040vvvvvvvvvvvvA 定义定义1313 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。若存在一条回路，经过每边一次且仅一次，则称这条回路为

9、欧拉回路。 具有欧拉回路的图称为欧拉图(E图)。在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路。定理定理3 3无向连通图G是欧拉图，当且仅当G中无奇点。定理定理4 4连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次。定理定理5 5已知图G*=G+E1无奇点，则 最小的充分必要条件为：(1) 每条边最多重复一次；(2) 对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半。1e1)()(EelEL|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题ACBEDGFIHJ KNML运动员乒乓球单打比赛定理定理6 6定义定义1414连通且不含圈的无向图称为树。树中次为1

10、的点称为树叶，次大于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中任意两点，有惟一链相连。一个图G 有生成树的充要条件是G 是连通图。 v1v2v3v4v5v1v2v3v4v5设图 是图G=(V , E )G=(V , E )的一支撑子图，如果图 是一个树,那么称K K 是G G 的一个生成树（支撑树），或简称为图G G 的树。图G G中属于生成树的边称为树枝，不在生成树中的边称为

11、弦。),(1EVK ),(1EVK 定义定义1515定理定理7 7（一）（一）避圈法避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与e1，e2不构成圈的边e3。一般设已有e1，e2，ek，找一条与e1，e2，ek中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止。e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4（二）（二）破圈法破圈法用破圈法求出下图的一个生成树。 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3

12、e4e5e6e7e8定义定义1616如果图 是图G的一个生成树，那么称E1上所有边的权的和为生成树T 的权，记作S(T)。如果图G的生成树T* 的权S(T*)，在G 的所有生成树T 中的权最小，即那么称T*是G 的最小生成树。 ),(1EVT )(min)(*TSTST 某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的电话线网，使电话线的总长度最短。 v1v2v3v4v5v66515723445v1v2v3v4v5v612344v1v2v3v4v514231352根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。|最小树的两种算法

13、算法1（Kruskal算法） 算法2（破圈法）|树根及其应用定义定义1717若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树。定义定义1818有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)。定义定义1919在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树。若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树。当m=2时，称为二叉树、完全二叉树。|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最

14、短。即： 最小。j iltsvv ,),( EVGj ilsv),(jivvjivv ,tv),()(jivvj ilL( (一一) )狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法适用于wij00，给出了从vs到任意一个点vj的最短路。Dijkstra算法是在1959年提出来的。目前公认，在所有的权wij 0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。算法步骤：算法步骤：1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T

15、标号。对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）。0)(svP), 3 , 2()(nivTiEvvji),()(, )(min)(j iijjlvPvTvT)(min)(ikvTvP例例9用Dijkstra算法求下图从v1到v8的最短路。 解解 （1）首先给v1以P标号，给其余所有点T标号。0)(1vP)8 , 3,2()(ivTi（2）（3）440,min)(, )(min)(12122lvPvTvT660,min)(, )(min)(13133

16、lvPvTvT（4）954,min)(, )(min)4(2424lvPvTvT844,min)(, )(min)(25255lvPvTvTv1v7v2v3v6v4v8v54594546467157比较所有T标号，T(v2)最小，令P(v2)=4，并记录路径(v1,v2)964,9min)(, )(min)(34344lvPvTvT876,8min)(, )(min)(35355lvPvTvT比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3)比较所有T标号，T(v5)最小，令P(v5)=8,并记录路径(v2,v3)1358,min)(, )(min)(56566lvPv

17、TvT1468,min)(, )(min)(57577lvPvTvT比较所有T标号，T(v4)最小，令P(v4)=9,并记录路径(v2,v4)1399,13min)(, )(min)(46466lvPvTvT1479,14min)(, )(min)(47477lvPvTvT比较所有T标号，T(v6)最小，令P(v6)=13,并记录路径(v5,v6)14513,14min)(, )(min)(67667lvPvTvT17413,min)(, )(min)(68688lvPvTvT比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v7,v8)15 114,17min)(, )(min

18、)(78788lvPvTvT因为只有一个T标号T(v8)最小，令P(v8)=15,并记录路径(v7,v8)， v1到v8之最短路为:v2v1v7v5v8 Dijkstra算法仅适合于所有的权wij=0的情形。如果当赋权有向图中存在有负权弧时，则该算法失效。算法的基本思路与步骤：首先：设任一点vi到任一点vj都有一条弧。 显然，从v1到vj的最短路是从v1出发，沿着这条路到某个点vi再沿弧(vi,vj)到vj。则v1到vi的这条路必然也是v1到vi的所有路中的最短路。设P1j表示从v1到vj的最短路长，P1i表示从v1到vi的最短路长，则有下列方程：开始时，令 即用v1到vj的直接距离做初始解。

19、第二步，使用递推公式： 求 ，当进行到第t步，若出现则停止计算， 即为v1到各点的最短路长。min11j iiijlPP), 2, 1(1) 1 (1njlPjj）（nklPPj ikiikj, 3,2min) 1(1)(1（二）逐次逼近法（二）逐次逼近法)(1kjP）（njPPtjtj,2,1)1(1)(1）（njPtj,2,1)(1例例10 求图中求图中v v1 1到各点的最短路到各点的最短路v1v2v3v4v5v6v7v85-324431-217-324(1)18(1)17(1)16(1)15(1)14(1)13(1)12(1)11PPPP3-P, 5P, 2P, 0P，解：初始条件为0

20、,3,5 ,2 , 00minP,.,P,P,PminP81111311112111111111111llll）（）（）（）（）（第一轮迭代：2,3,5 , 02 , 20minP,.,P,P,PminP82(1)1832(1)1322(1)1212(1)11(2)12llll(2)18(2)17(2)16(2)15(2)14(2)13PP,11P, 6P, 3P, 0P类似可得v1v2v3v4v5v6v7v8P1j(1)P1j (2)P1j (3)P1j (4)P1j (5)P1j (6)v1025 -3 000000v20 -2 4 22222-5v3 0 6 500000v4 40 -3

21、-3-3-3-3-3v5 0 66333v6 -304 116666v7 7 2 0 1499v8 3 -10 15101010表中最后一列数字表示v1到各点的最短路长例11 求：5年内，哪些年初购置新设备，使5年内的总费用最小。 解：（1）分析：可行的购置方案（更新计划）是很多的，如： 1 ) 每 年 购 置 一 台 新 的 ， 则 对 应 的 费 用 为 ：11+11+12+12+13+5+5+5+5+5=842)第一年购置新的，一直用到第五年年底，则总费用为：11+5+6+8+11+18=59 显然不同的方案对应不同的费用。 第i年度 1 2 3 4 5购置费 11 11 12 12 1

22、3设备役龄0-1 1-2 2-3 3-4 4-5维修费用 5 6 8 11 18 （2）方法：将此问题用一个赋权有向图来描述，然后求这个赋权有向图的最短路。 求解步骤： 1）画赋权有向图： 设 vi 表示第i年初，(vi ,vj )表示第i 年初购买新设备用到第j年初（j-1年底），而Wij表示相应费用，则5年的一个更新计划相当于从v1 到v6的一条路。 2）求解 （标号法） 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=59 W23 =11+5=16 W24 =11+5+6=2

23、2W25 =11+5+6+8=30 W26 =11+5+6+8+11=41 W45 =12+5=17 W46 =12+5+6=23W56 =13+5=18 W34 =12+5=17W35 =12+5+6=23W36 =12+5+6+8=31 其他，当的距离到为，令网络中的权矩阵为EvvldvvldDjiijijjiijnnij)()(算法基本步骤为：DD)0(1）输入权矩阵（三）（三）FloydFloyd算法算法可直接求出网络中任意两点间的最短路；,min),.,3 , 2 , 1()()2()1()1()1(n)()(kkjkikkijijnkijkddddnkdD其中，计算的最短路长到就是

24、中元素jinijnnijvvddD)(n)()n()()3(|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。vsv2v3v4v1vt33244242321上图可看作输油管道网，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大?网络

25、D上的流，是指定义在弧集合E上的一个函数其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量。 ),(jijifvvff 定义定义2020设一个赋权有向图D=（V, E）,在V中指定一个发点vs和一个收点vt ,其它的点叫做中间点。对于D中的每一个弧（vi , vj）E ,都有一个非负数cij,叫做弧的容量。我们把这样的图D叫做一个容量网络，简称网络，记做D=（V，E，C）。称满足下列条件的流为可行流：（1）容量条件：对于每一个弧（vi ,vj）E有0 fij cij 。 （2）平衡条件：对于发点vs，有对于收点vt ，有对于中间点，有EvvEvvsjjsjssjWff),(),(-

26、EvvEvvt jjtjttjWff),(),(-EvvEvvi jjijiijff),(),(0可行流中 fijcij 的弧叫做饱和弧，fijcij的弧叫做非饱和弧。fij0 的弧为非零流弧，fij0 的弧叫做零流弧。 定义定义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, )。SSSSS定理定理1111设f为网络G=(V,E,C)的任一可行流，流量为W，(S，)是分离v

27、s,vt的任一割集，则有WC(S, )。SS定理定理1010(最大流-最小割定理)任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量。可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链。 定义定义2222容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示。f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条增广链 ),(0),(0jij ij ijij ij ivvcfvvcf即 中的每一条弧都是非饱和弧 即 中的每一条弧

28、都是非零流弧 推论推论 设已有一个可行流f，标号的方法可分为两步： 第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。 从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流。一、标号过程：1给发点vs 标号（0，+）。2取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 ，且 ，那么给vj 标号 ，其中：（2）如果边 ，且 ，那么给vj 标号 ，其中： 3重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束。若vt被标号，则存在一条增广链，转调整

29、过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流。Evvij),(0i jf),(jiv),min(ii jjfEvvji),(ijijcf),(jiv),min(ijijijfc二、调整过程设1令 2去掉所有标号，回到第一步，对可行流重新标号。),(min1jijijivvfc),(min2jijivvf),min(21),(),(),(jijijijijijijivvfvvfvvff例14求下图所示网络中的最大流，弧旁数为),(jijifc(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(5 ,2)(2 , 2)(4 ,2)(3

30、 ,3)v5(2 ,2)(4 ,2)图8-40解.用标号法。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已得到标号，说明存在可增广链，所以标号过程结束。(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(

31、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-412.转入调整过程令=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-

32、41中的粗线边，调整后的可行流见图8-42（，+）（ +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，即为最大流的流量，算法结束。|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题 最小费用流问题的一般提法： 已知容量网络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为最大流时，此问题即为最小费用最大流问题。最小费用流问题的常用算法有两种： 原始算法； (2) 对偶算法。(1)下面只介绍第二种算法，本算