运筹学胡运权第08章.ppt

第八章 图与网络分析(Graph Theory and Network Analysis)本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题BDACABCD哥尼斯堡七空桥哥尼斯堡七空桥一笔画问题一笔画问题§1图与网络的基本知识环球旅行问题环球旅行问题一个图是由点集V={vj}和V中元素的无序对的一个集合E={ek}构成的二元组，记为G =(V,E),其中V 中的元素vj 叫做顶点，V表示图G的点集合；E中的元素ek 叫做边，E 表示图 G 的边集合v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10例例图图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) , (v2 , v3 ) ,(v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) }图图2图及其分类一条边的两个端点是相同的,那么称为这条边是环。

如果两个端点之间有两条以上的边，那么称为它们为多重边一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图每一对顶点间都有边相连的无向简单图称为完全图有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图定义定义2 2定义定义3 3图及其分类定义定义4 4图G=(V,E)的点集V可以分为两个非空子集X，，Y，即X∪∪Y=V,X∩Y=，使得E中每条边的两个端点必有一个端点属于X，另一个端点属于Y，则称G为二部图(偶图)，有时记作G=(X,Y,E)X:{v1, v3, v5}Y:{v2, v4, v6}v1v3v5v6v4v2图及其分类v1v2v3v4v5v6e1e2e3e4e5e6e7e8e9e10度为零的点称为弧立点，度为1的点称为悬挂点悬挂点的关联边称为悬挂边度为奇数的点称为奇点，度为偶数的点称为偶点以点v为端点的边的个数称为点v 的度（次），记作 图中d(v1)= 4，d(v6)= 4（环计两度）定义定义5 5顶点的次有向图中，以vi为始点的边数称为点vi的出次，用 表示；以vi为终点的边数称为点vi 的入次，用 表示；vi 点的出次和入次之和就是该点的次。

所有顶点的入次之和等于所有顶点的出次之和定理定理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中指定两个点，一个称为始点（或发点），记作v1 ，一个称为终点（或收点），记作vn ，其余的点称为中间点对每一条弧 ，对应一个数 ，称为弧上的“权”通常把这种赋权的图称为网络 定义定义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是同一个点时，称此链为圈圈中既无重复点也无重复边者为初等圈定义定义9 9定义定义1010一个图中任意两点间至少有一条链相连，则称此图为连通图任何一个不连通图都可以分为若干个连通子图，每一个称为原图的一个分图对于有向图可以类似于无向图定义链和圈，初等链、圈，此时不考虑边的方向而当链(圈)上的边方向相同时，称为道路(回路)对于无向图来说，道路与链、回路与圈意义相同对于网络（赋权图）G=（（V,E））, ,其中边有权 ，构造矩阵 ，其中：称矩阵A为网络G的权矩阵设图G=（（V,E））中顶点的个数为n，构造一个矩阵 ，其中： 称矩阵A为网络G的邻接矩阵 定义定义1111定义定义1212图的矩阵表示当G为无向图时，邻接矩阵为对称矩阵例例权矩阵为：邻接矩阵为：邻接矩阵为：v5v1v2v3v4v64332256437图的矩阵表示欧拉回路与中国邮路问题定义定义1313 连通图G中，若存在一条道路，经过每边一次且仅一次，则称这条路为欧拉道路。

若存在一条回路，经过每边一次且仅一次，则称这条回路为欧拉回路 具有欧拉回路的图称为欧拉图(E图)在引言中提到的哥尼斯堡七桥问题就是要在图中寻找一条欧拉回路定理定理3 3无向连通图G是欧拉图，当且仅当G中无奇点定理定理4 4连通有向图G是欧拉图，当且仅当它每个顶点的出次等于入次欧拉回路与中国邮路问题定理定理5 5已知图G*=G+E1无奇点，则 最小的充分必要条件为：(1) 每条边最多重复一次；(2) 对图G中每个初等圈来讲，重复边的长度和不超过圈长的一半本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题§2树ACBEDGFIHJ KNML运动员乒乓球单打比赛树的概念和性质定理定理6 6定义定义1414连通且不含圈的无向图称为树树中次为1的点称为树叶，次大于1的点称为分枝点图T=(V,E),|V|=n,|E|=m，则下列关于树的说法是等价的1) T是一个树2) T无圈，且m=n-13) T连通，且m=n-14) T无圈，但每加一新边即得惟一一个圈5) T连通，但任舍去一边就不连通6) T中任意两点，有惟一链相连一个图G 有生成树的充要条件是G 是连通图。

v1v2v3v4v5v1v2v3v4v5设图 是图G=(V , E )G=(V , E )的一支撑子图，如果图 是一个树,那么称K K 是G G 的一个生成树（支撑树），或简称为图G G 的树图G G中属于生成树的边称为树枝，不在生成树中的边称为弦定义定义1515定理定理7 7图的生成树（一）（一）避圈法避圈法 在图中任取一条边e1，找一条与e1不构成圈的边e2，再找一条与{e1，e2}不构成圈的边e3一般设已有{e1，e2，…，ek}，找一条与{e1，e2，…，ek}中任何一些边不构成圈的边ek+1，重复这个过程，直到不能进行为止e5v1v2v5e2e3e1e6e7e8e4v4v1v2e1v3e2e4v4v5e6v3v1v2v3v5e1e6e8e4v4（二）（二）破圈法破圈法用破圈法求出下图的一个生成树 v1v2v3v4v5e1e2e3e4e5e6e7e8v1v2v3v4v5e2e4e6e8v1v2v3v4v5e1e2e3e4e5e6e7e8最小生成树问题定义定义1616如果图 是图G的一个生成树，那么称E1上所有边的权的和为生成树T 的权，记作S(T)。

如果图G的生成树T* 的权S(T*)，在G 的所有生成树T 中的权最小，即那么称T*是G 的最小生成树 某六个城市之间的道路网如图所示，要求沿着已知长度的道路联结六个城市的线网，使线的总长度最短 v1v2v3v4v5v66515723445v1v2v3v4v5v612344v1v2v3v4v514231352根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的|最小树的两种算法 算法1（Kruskal算法） 算法2（破圈法）|树根及其应用定义定义1717若一个有向图在不考虑边的方向时是一棵树，则称这个有向图为有向树定义定义1818有向树T，恰有一个结点入次为0，其余各点入次均为1，则称T为根树(又称外向树)定义定义1919在根树中，若每个顶点的出次小于或等于m，称这棵树为m叉树若每个顶点的出次恰好等于m或零，则称这棵树为完全m叉树当m=2时，称为二叉树、完全二叉树本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题最短路的一般提法为：设 为连通图，图中各边 有权 （ 表示 之间没有边）， 为图中任意两点，求一条路 ，使它为从 到 的所有路中总权最短。

即： 最小§3最短路问题( (一一) )狄克斯屈拉狄克斯屈拉(Dijkstra)算法算法适用于wij≥0≥0，给出了从vs到任意一个点vj的最短路Dijkstra算法是在1959年提出来的目前公认，在所有的权wij ≥0时，这个算法是寻求最短路问题最好的算法并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路算法步骤：算法步骤：1.给始点vs以P标号 ，这表示从vs到 vs的最短距离为0，其余节点均给T标号， 2.设节点 vi 为刚得到P标号的点，考虑点vj，其中 ，且vj为T标号对vj的T标号进行如下修改：3.比较所有具有T标号的节点，把最小者改为P标号，即：当存在两个以上最小者时，可同时改为P标号若全部节点均为P标号，则停止，否则用vk代替vi，返回步骤（2）例例9用Dijkstra算法求下图从v1到v8的最短路 解解 （1）首先给v1以P标号，给其余所有点T标号。

2）（3）（4）v1v7v2v3v6v4v8v54594546467157比较所有T标号，T(v2)最小，令P(v2)=4，并记录路径(v1,v2)比较所有T标号，T(v3)最小，令P(v3)=6,并记录路径(v1,v3)比较所有T标号，T(v5)最小，令P(v5)=8,并记录路径(v2,v3)比较所有T标号，T(v4)最小，令P(v4)=9,并记录路径(v2,v4)比较所有T标号，T(v6)最小，令P(v6)=13,并记录路径(v5,v6)比较所有T标号，T(v7)最小，令P(v7)=14,并记录路径(v7,v8)因为只有一个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的直接距离做初始解。

第二步，使用递推公式： 求 ，当进行到第t步，若出现则停止计算， 即为v1到各点的最短路长二）逐次逼近法（二）逐次逼近法例例10 求图中求图中v v1 1到各点的最短路到各点的最短路v1v2v3v4v5v6v7v85-32443－－1-217-324解：初始条件为第一轮迭代：类似可得v1v2v3v4v5v6v7v8P1j(1)P1j (2)P1j (3)P1j (4)P1j (5)P1j (6)v1025 -3    000000v20  -2  4   22222-5v3 0 6  500000v4  40   -3-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      13设备役龄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=22W25 =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 （三）（三）FloydFloyd算法算法可直接求出网络中任意两点间的最短路；本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题§4最大流问题 最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等。

20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分问题引入vsv2v3v4v1vt33244242321上图可看作输油管道网，vs为起点，vt为终点，v1,v2,v3,v4为中转站，边上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大?网络D上的流，是指定义在弧集合E上的一个函数其中f(vi ,vj) =fij 叫做弧(vi，vj)上的流量 最大流有关概念定义定义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 ，有对于中间点，有可行流中 fij＝cij 的弧叫做饱和弧，fij＜cij的弧叫做非饱和弧fij＞0 的弧为非零流弧，fij＝0 的弧叫做零流弧。

定义定义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, )最大流-最小流定理定理定理1111设f为网络G=(V,E,C)的任一可行流，流量为W，(S，)是分离vs,vt的任一割集，则有W≤C(S, )定理定理1010(最大流-最小割定理)任一个网络G中，从vs到vt的最大流的流量等于分离vs、vt的最小割的容量可行流f 是最大流的充分必要条件是不存在从vs到vt 的关于f 的一条可增广链 定义定义2222容量网络G，若 为网络中从vs到vt的一条链，给 定向为从vs到vt， 上的弧凡与 方向相同的称为前向弧，凡与 方向相反的称为后向弧，其集合分别用 和 表示f 是一个可行流，如果满足： 则称 为从vs到vt 的关于f 的一条增广链即 中的每一条弧都是非饱和弧即 中的每一条弧都是非零流弧推论推论求最大流的标号算法 设已有一个可行流f，标号的方法可分为两步： 第1步是标号过程，通过标号来寻找可增广链；第2步是调整过程，沿可增广链调整f以增加流量。

从网络中的一个可行流f出发（如果D中没有f，可以令f是零流），运用标号法，经过标号过程和调整过程，可以得到网络中的一个最大流一、标号过程：1．给发点vs 标号（0，+∞）2．取一个已标号的点vi，对于vi一切未标号的邻接点vj 按下列规则处理：（1）如果边 ，且 ，那么给vj 标号 ，其中：（2）如果边 ，且 ，那么给vj 标号 ，其中： 3．重复步骤2，直到vt被标号或标号过程无法进行下去，则标号结束若vt被标号，则存在一条增广链，转调整过程；若vt未被标号，而标号过程无法进行下去，这时的可行流就是最大流二、调整过程设1．令 2．去掉所有标号，回到第一步，对可行流重新标号例14求下图所示网络中的最大流，弧旁数为(3 ,3)v2v1v4v6vsvtv3(3,0)(5 , 5)(3 , 2(5 , 4)(5 ,2)(2 , 2)(4 ,2)(3 ,3)v5(2 ,2)(4 ,2)图8-40解.用标号法。

1.标号过程 1）首先给vs标号（0，+∞） 2）看vs:在弧(vs,v1)上,fs2=2

按v1点标号找到点v5，由于标号为-v5,(v5,v1)为反向边，令f15′=f15-2由v5点的标号再找到v2，令f25′=f25+2由v2点找到vs，令fs2′=fs2+2调整过程结束，调整中的可增广链见图8-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，即为最大流的流量，算法结束本章内容|图与网络的基本知识|树|最短路问题|最大流问题|最小费用流问题§5最小费用流问题 最小费用流问题的一般提法： 已知容量网络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为最大流时，此问题即为最小费用最大流问题最小费用流问题的常用算法有两种：(1)原始算法；(2)(2) 对偶算法3)下面只介绍第二种算法，本算法是有效算法§5最小费用流问题已知网络G =（V，E，C，d），f是G上的一个可行流， 为一条从vs到vt的增广链， 称为链的费用定义定义2424若 * 是从vs到vt的增广链中费用最小的增广链，则称 * 是最小费用增广链定理定理1212若f是流量为W(f)的最小费用流， 是关于f的从vs到vt的一条最小费用可增广链，则f经过 调整流量θ得到新可行流f′(记为f′=fμθ)，一定是流量为W(f)+θ的可行流中的最小费用流1.当 ，令寻找关于f 的最小费用增广链： 构造一个关于f 的赋权有向图L(f ) ，其顶点是原网络G的顶点，而将G中的每一条弧 (vi,vj)变成两个相反方向的弧（vi,vj）和(vj ,vi)，并且定义图中弧的权lij为：在网络G中寻找关于f 的最小费用增广链等价于在L(f )中寻求从vs 到vt 的最短路。

2.当（vj,vi）为原来网络G中(vi, vj)的反向弧,令步骤：（1）取零流为初始可行流 ，f (0) ={0}2）一般地，如果在第k-1步得到最小费用流 f (k-1)，则构造图 L( f (k-1) )3）在L( f (k-1) )中，寻求从vs到vt的最短路若不存在最短路，则f (k-1)就是最小费用最大流；否则转(4)4）如果存在最短路，则在可行流f (k－1)的图中得到与此最短路相对应的增广链，在增广链上，对f (k－1)进行调整，调整量为：令得到新可行流f (k) 对f (k)重复上面步骤，返回（2）例例16  在在图8-48所示运输网络上求流量v为10的最小费用最大流，弧旁权是（cij , dij） （ 10 ,4）vsv2v3vtv1（5 ,2）（ 7 ,1）（2 ,6）（4 ,2）（ 10 ,3）（8 ,1）4vsv2v3vtv1216231L(f(0))0vsv2v3vtv1550005f(1)2vsv2v3vtv1570005f(2)1L(f(1))4vsv2v3vtv1-2-1623-1d(f(1))=5×1+5×2+5×1=20d(f(2))=4×2+5×1+5×2+7×1=301L(f(2))4vsv2v3vtv1-2-1623-1-42vsv2v3vtv1570338f(3)d(f(3))=2×4+8×1+5×2+3×3+3×2+7×1=48f(3)即为所求的最小费用流。