图与网络模型及方法讲课稿

1、图与网络模型及方法|图与子图|图的连通与割集|树与支撑树|最小树|最短有向路|最大流|最小费用流|最大对集|图论中所谓的“图”是指某类具体事物和这些事物之间的联系。|如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。|图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。这个图是连通的，且每个点都与偶数线相关联这个图是连通的，且每个点都与偶数线相关联|图与网络是运筹学（Operations Research）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、

2、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域|的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。图-由若干个点和连接这些点的连线所组成的图形vi图中的点，称为顶点（代表具体事物，研究对象。ei图中的连线，称为边（对象之间的联系）m(G)=|E|G的边数，简记为mn(G)= |V|G的顶点数，简记为n一.图的概念记V=vi点的集合，E= ei边的集合G=V，EG 一个图1v2v3v4v5v1e2e3e4e5e6em=6,n=5,jikvve 图的基本概念有向图无向图边e=(vi, vj)有方向vi为始点，vj为终点边e=(vi, vj)无方向， 此时(vi,

3、 vj)=(vj,vi) e4=(v3，v4） =(v4， v3）e4=(v3，v4)(v4，v3）e5=(v3，v4） =(v4， v3）此时(vi, vj)(vj,vi) 1v2v3v4v1e2e3e4e5e6e1v2v3v4v1e2e3e4e5e6ee5=(v4，v3)(v3，v4)图有向图无向图二.常用名词：1v2v3v4v1e2e3e4e5e6e1、端点和关联边：的关联边和点是的端点，边是边、则称点若jikkjijikvveevvEvve,2、相邻点和相邻边：边边称为相邻边，简称邻端点落在同一个顶点的相邻点，简称邻点，一条边的两个端点称为3、多重边与环：点的边称为环。两个端点落在同一

4、个顶多重边或平行边；具有相同端点的边称为4、多重图和简单图：无环也无多重边的图称为简单图。含有多重边的图称为多重图；5、次：)(iiivdvv的次，点为端点的边的条数称为以点6、悬挂点和悬挂边：次为1的点称为悬挂点，与悬挂点相联的边称为悬挂边。7、孤立点：8、奇点与偶点：的点称为孤立点次为0点，次为偶数的点称为偶次为奇数的点称为奇点1v2v3v4v2e3e4e5e1e5v6v6e, 3)(1vd为悬挂点，、62vv为悬挂边，、52ee为孤立点，5v4)(3vd, 1)(2vd, 3)(4vd, 0)(5vd, 1)(6vd为奇点，、6421vvvv为偶点、35vv)(ivd12，G的边数m=6

5、mvdi2)(即性质性质1 1：在图：在图G=(V,E)G=(V,E)中，所有点的次之和是边数中，所有点的次之和是边数m m的两倍。的两倍。证明：由于每条边均与两个顶点关联，因此在计算顶点的次时每条边都计算了两遍，所以顶点次数的总和等于边数的二倍。三三. .次（度）的性质次（度）的性质性质性质2 2：在任何图：在任何图G=(V,E)G=(V,E)中，中，奇点的个数为偶数奇点的个数为偶数证明：设V1，V2分别是图G中奇点和偶点的集合，则V1V2=V, V1V2=,有性质1， ，因为V2是偶点的集合，d(vi)(iV2)均为偶数，所以mvdvdvdViiViiVii2)()()(21为偶数所以2)

6、(Viivd为偶数1)(Viivd是奇点的集合而1,V均为奇数)(,1Vivdi只有偶数个奇数相加才能得到偶数，所以V1中的点，即奇点的个数为偶数。四四. . 链、路、连通图链、路、连通图1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1.链：对于无向图G=(V，E)，若图G中有一个点与边的交替序列 =vi0,ei1,vi1,ei2,vik-1,eik,vik，且eit=(vit-1,vit)(t=1,2,k),则称该交替序列 为连结vi0和vik的一条链。 简单链：简单链：中只有重复的点而无重复边者为简单链。初等链：初等链：中没有重复的点和重复边者为初等链。圈：圈：无向图G中，连

7、结 vi0与vik的一条链，当vi0与vik是同一个点 时，称此链为圈。圈中只有重复点而无重复边者为简单圈， 既（除起点、终点重复外）无重复点也无重复边者为初等圈,48176vevev不是链,17556vevev初等链evevevevev简单链1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e为一个圈,5443322948175vevevevevevev为一个圈,544816655vevevevev（简单圈）（初等圈）2 路路：在有向图D=(V，A)中，若有从vi0到vik不考虑方向的链，且各边方向一致，则称之为从vi0到vik的一条路。 对于有向图可以类似

8、于无向图定义链和圈，初等链、圈，简单链、圈此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e1v2v3v4v2e3e4e1e5v6e3 连通图连通图：一个图中任意两点间至少有一条链(或路)相连的图。 连通图非连通图五网络 在实际问题中，往往只用图来描述所研究对象之间的关系还不够，与图联系在起的，通常还有与点或边有关的某些数量指标，通常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种带有某种数量指标的图称为网络(赋权图)。如公路交通图：vi表示城市,ei表示公路

9、w(ei)表示公路ei的长度如w(e2)=50表示城市v2与城市v3之间的距离是50千米1e2e3e4e5e6e1v2v3v4v5v6v7e8e9e六. 完全图、偶图1完全图： 一个简单图，若任意两个顶点之间均有一条边相连，则称这样的图为完全图。 对于完全图，由于每个顶点与所有其余顶点都有一条边相连，所以在有n个顶点的完全图中，各个顶点的次均为（n-1）。2.偶图：若图G的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中的任意两个顶点均不相邻，称这样的图为偶图，也称为二部图。若偶图的顶点集合V1，V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。v2v3v4v5v2v3v

10、4v5v1v1完全图(完全)偶图定理定理 一个图为偶图的充分必要条件该图无奇圈一个图为偶图的充分必要条件该图无奇圈七.子图、部分图对于图G1=V1,E1和图G2=V2,E2,若有 ，称G1是G2的一个子图。若有 ，称G1是G2的一个部分图（生成子图）。2121EEVV和2121EEVV和* 部分图也是子图，但子图不一定是部分图。生成子图七.子图、部分图* 部分图也是子图，但子图不一定是部分图。生成子图2121EEVV和2121EEVV和对于图G1=V1,E1和图G2=V2,E2,若有 ，称G1是G2的一个子图。若有 ，称G1是G2的一个部分图（生成子图）。八.前向弧与后向弧设是一条从vs到vt

11、的链，则链上与链的方向一致的弧称为前向弧，记这些弧为+；链上与链的方向相反的弧称为后向弧，记这些弧为-。vsv1v2v3v4v5vt前向弧与后向弧|子图子图 设设 G1 = V1 , E1 , G2 = V2 , E2 子图定义：子图定义：如果 V2 V1 , E2 E1 称 G2 是 G1 的子图；真子图：真子图：如果 V2 V1 , E2 E1 称 G2 是 G1 的真子图；部分图：部分图：如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图；导出子图：导出子图：如果 V2 V1 , E2 = vi , vj vi , vj V2 ，称 G2 是 G1 中由V2 导出的导出子

12、图。九、图的矩阵表示 用矩阵表示图对研究图的性质及应用常常是比较方便的定义：网络(赋权图)G(V，E)，其边(vi,vj)有权ij,构造矩阵A=(aij)nn,其中：其它0E)v,v(ajiijij称矩阵A为网络G的权矩阵。例、写出下图的权矩阵v1v2v3v4v57654249380650760844580320430974290A定义：对于图G(V，E)，|V|=n,构造一个矩阵A=(aij)nn,其中：其它0E)v,v(1ajiij称矩阵A为图G的邻接矩阵。例、写出下图的邻接矩阵v1v3v5v2v4v6当G为无向图时，邻接矩阵为对称矩阵010000101010100010010010000

13、100000110A654321vvvvvv654321vvvvvv|给出了一个连接若干个城镇的铁路网络，在这个给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。网络的两个指定城镇间，找一条最短铁路线。|以各城镇为图以各城镇为图G 的顶点，两城镇间的直通铁路为的顶点，两城镇间的直通铁路为图图G 相应两顶点间的边，得图相应两顶点间的边，得图G 。对。对G 的每一边的每一边e，赋以一个实数赋以一个实数w(e)直通铁路的长度，称为直通铁路的长度，称为e的权，的权，得到赋权图得到赋权图G 。G 的子图的权是指子图的各边的的子图的权是指子图的各边的权和。权和。|问题就是求

14、赋权图问题就是求赋权图G 中指定的两个顶点中指定的两个顶点u0 ,v0间的间的具最小权的轨。这条轨叫做具最小权的轨。这条轨叫做u0 ,v0间的最短路，它间的最短路，它的权叫做的权叫做u0 ,v0间的距离，亦记作间的距离，亦记作d(u0 ,v0)|基本思想 是按距 u 0从近到远为顺序，依次求得u 0到G 的各顶点的最短路和距离，直至v 0 （或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。定义：连通且不含圈的无向图称为树。记作T(V，E)二、二、 树树|树可以有很多等价的定义,以下定理中的各命题都体现树的特征.定理 设G=V,E是一无向图，|V|=n，|E|

15、=m。则以下命题是等价的.(1) G是树;(2) G的每对顶点之间有唯一的一条路;(3) G连通且m=n-1;(4) G无圈且m=n-1;(5) G无圈,在G的任一对顶点上加一新边后产生圈;(6) G连通，但删去任何一边后不再连通。 定理：无向图G有生成树当且仅当G连通。证明: 必要性显然, 只证充分性。若G无圈，则G本身就是G的生成树。若G有圈C，则在G中删去C的一条边，所得的图是连通的，继续这个过程，直到所得的图T无圈为止，则T就是G的一棵生成树。定义： 若图G的生成子图是一棵树，则称该树为G的生成树(支撑树)。或简称为图G的树(b)为(a)图的生成树最小生成树的求法：避圈法与破圈法定义：

16、 树的各条边称为树枝。一般图G的生成树有多个，称其中树枝总长度最小的生成树为最小树。避圈法：在图G中，每步选出一条边e，使它与已选边不构成圈，且e是未选边中长度最小的边，直到选够 n-1 边为止。v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232破圈法：从网络图N中任取一回路，去掉该回路中权数最大的一条边，得一子网络图N1。在N1中再任取一回路，去掉该回路中权数最大的一条边，得一子网络图N2。如此继续下去，

17、直到剩下的子图中不再含回路为止。该子图就是N的最小生成树。v1v2v3v8v7v6v5v4v04112131444523552|欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为wij，设计一个线路图使总造价最低|连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生 成树叫做最小生成树|造最小生成树的两种常用算法-prim 算法与Kruskal 算法。|设置两个集合P 和Q,其中P 用于存放G 的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为 1 P = v （假设构造最小生成树时，从顶点 v 1出发），集合Q的初值为Q = 。|prim算法的思

18、想是：从所有pP，vV P的边 中 ，选取具有最小权值的边pv ，将顶点v 加入集合P 中，将边pv 加入集合Q中，如此不断重复，直到P =V 时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。|定义 1： 经过G 的每条边的迹叫做G 的Euler 迹；闭的Euler 迹叫做Euler 回路或E回路；含Euler 回路的图叫做Euler 图。|直观地讲，Euler 图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。|定理6 （i）G 是Euler 图的充分必要条件是G 连通且每顶点皆偶次。|（ ii ） G 是Euler 图的充分必要条件是G

19、 连通且|（iii）G 中有Euler 迹的充要条件是G 连通且至多有两个奇次点。|定义 包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton 轨叫做Hamilton 圈或H 圈；含Hamilton 圈的图叫做Hamilton 图。|直观地讲，Hamilton 图就是从一顶点出发每顶点恰通过一次能回到出发点的那种 图，即不重复地行遍所有的顶点再回到出发点。|中国邮递员问题 一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。|中国邮递员问题的数学模型：在一个赋权连通图上求一个含所有边的回路，且使

20、此回路的权最小。|若此连通赋权图是 Euler 图，则可用Fleury 算法求Euler 回路，此回路即为所求。|对于非 Euler 图，1973 年，Edmonds 和Johnson 给出下面的解法：|邮局有k(k 2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。|kPP 的数学模型如下：|一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？|是在一个赋权完全图中，找出一个有最小权的Hamilton 圈。称这种圈为最优圈

21、|与最短路问题及连线问题相反，目前还没有求解与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。获得相当好（但不一定最优）的解。1957 年，贝尔热(Berge)得到最大对集的充要条件：|定理2 M 是图G 中的最大对集当且仅当G 中无M 可增广轨。1935 年，霍尔(Hall)得到下面的许配定理：|定理 3 G 为二分图， X 与Y 是顶点集的划分，G 中存在把X 中顶点皆许配的对集的充要条件是，S X ，则| N(S) | S |，其中N(S)是S 中顶点的邻集。|推论 1：若G 是k

22、 次（k 0)正则2分图，则G 有完美对集。|所谓 k 次正则图，即每顶点皆k 度的图。由此推论得出下面的婚配定理：|定理定理 4 每个姑娘都结识 k(k 1)位小伙子，每个小伙子都结识k 位姑娘，则每位姑娘都能和她认识的一个小伙子结婚，并且每位小伙子也能和他认识的一个姑娘结婚。|工作人员 x 1, x2 , , xn 去做n件工作y 1, y 2, , y n ，每人适合做其中一件或几件，问能否每人都有一份适合的工作？如果不能，最多几人可以有适合的工作？|这个问题的数学模型是： G 是二分图，顶点集划分为V (G) = X UY ，|X = x1, , x n ， Y = y1, , y n

23、 ，当且仅当x i适合做工作y j时，x i y j E(G) ，求G 中的最大对集。|1965 年埃德门兹(Edmonds)提出匈牙利算法。|匈牙利算法：|（i）从G 中任意取定一个初始对集M 。|（ii）若M 把X 中的顶点皆许配，停止，M 即完美对集；否则取X 中未被M 许|配的一顶点u，记S = u，T = 。|（iii）若N(S) = T ，停止，无完美对集；否则取yN(S) T 。|（iv）若y 是被M 许配的，设yzM ，S = S Uz，T = T Uy，转（iii）；|否则，取可增广轨P(u, y)，令M = (M E(P) U(E(P) M)，转（ii）。|在人员分派问题中

24、，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。|这 个 问 题 的 数 学 模 型 是 ： 在 人 员 分 派 问 题 的 模 型 中 ， 图 G 的每边加了权|w (x i ， y j ) 0 表示 x i干 y j工作的效益，求加权图G 上的权最大的完美对集。|解决这个问题可以用库恩曼克莱斯（Kuhn-Munkres）算法|定义 若映射l :V(G) R，满足x X , yY ，l(x) + l( y) w(x, y)，|则称 l 是二分图G 的可行顶点标号。|令El = xy | xy E(G),l(x) + l( y) =w(xy) ，称以

25、l E 为边集的G 的生成子图为相等子图，记作G l 。|可行顶点标号是存在的。例如定理5 G l的完美对集即为G 的权最大的完美对集。最短路问题 最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以便用这个模型如设备更新、管道铺设、线路安排、厂区布局等。 最短路问题的一般提法：设G=V，E为连通图，图中各边(vi,vj)有权lij(lij=表示vi,vj间无边)。vs,vt为图中任意两点，求一条路，使它是从vs到vt的所有路中总权最小的路。即)v,v(ijjil)(L最小有些最短路问题是求网络中某指定点到其余所有点的最短路，或求网络中任意两点间的最短路。下面介绍三种算法，可分别用于求

26、解这几种最短路问题。使用条件网络中所有的弧(边)权均，即：0lij(1) 基本思路基于以下原理：若序列vs,v1,vn-1,vn是从vs到 vn的最短路，则序列vs,v1,vn-1必为从vs到vn-1的最短路。 1、Dijkstra算法本算法由Dijkstra于1959年提出，可用于求解指定两点vs、vt间的最短路，或从指定点vs到其余各点的最短路。下面给出Dijkstra算法基本步骤，采用标号法。可用两种标号：T标号与P标号，T标号为试探性标号，P为永久性标号，给vi点一个P标号时，表示从vs到点vi的最短路权,vi点的标号不再改变。给vi点一个T标号时表示从vs到点vi的估计最短路权的上界

27、，是一种临时标号凡没有得到P标号的点都有T标号。算法每一步都把某一点的T标号改为P标号，当终点vt得到P标号时，全部计算结束。对于有n个顶点的图，最多经n一1步就可以得到从始点到终点的最短路。标号的意义： 标号P(永久性标号)从始点到该标号点的最短路权。 标号T(临时性标号从始点到该标号点的最短路权。第二步：若vi为刚得到P标号的点，考虑这样的点vj：(vi,vj)属于E，且vj为T标号。对vj的T标号进行如下的更改：T(vj)=minT(vj),P(vi)+lij第三步：比较所有具有T标号的点，把最小者改为P标号，即 第一步：给始点vs标上永久性标号P(vs)=0，其余各点标临时性标号 T(

28、vj)=+,vTmin)v(PiTvii标号为当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用 代vi转回第二步。iv例、用Dijkstar算法求下图中v1到v7点的最短路。v1v3v2v7v5v4v6171344452572(1) 首先给v1以P标号,P(v1)=0,其余所有点给T标号,T(vi)=+（图中( )内的数表示P标号； 内的数表示T标号）v1(0)v2v7v5v411344452572v3v67v1(0)v2v7v5v411344452572v32v645(2)由于边(v1,v2)、(v1,v3) 、(v1,v4)属于E，且v2,v3,v4为T标号，所以

29、修改这三个点的标号：T(v2)=minT(v2),P(v1)+l12=min,0+4=4T(v3)=minT(v3),P(v1)+l13=min,0+2=2 T(v4)=minT(v4),P(v1)+l14=min,0+5=57(3) 比较所有T标号，T(v3)最小，所以令P(v3)=2v1(0)v2v7v5v411344452572v3(2)v6457v1(0)v2v7v5v411344452572v3(2)v64497(4) v3为刚得到P标号的点，考察边(v3,v4),(v3,v6)的端点v4,v6。T(v4)=minT(v4),P(v3)+l34=min5,2+2=4T(v6)=min

30、T(v6),P(v3)+l36=min,2+7=9(5) 比较所有T标号，T(v2), T(v4)最小，所以令P(v2)=P(v4) =4v1(0)v2v7v5v411344452572v3(2)v6(4)(4)97(6) v2,v4为刚得到P标号的点,考察边(v2,v5), ),(v4,v5),(v4,v6)的端点v5,v6。T(v5)=minT(v5),P(v4)+l45,P(v2)+l25=min,4+3,4+4=7T(v6)=minT(v6),P(v4)+l46=min9,4+4=8v1(0)v2v7v5v411344452572(4)(4)877v3(2)v6(7) 比较所有T标号，

31、T(v5)所以令P(v5) =7v1(0)v2v7v5v411344452572(4)(4)(7)8v3(2)v6v1(0)v2v7v5v411344452572(4)(4)(7)148v3(2)v6(8) v5为刚得到P标号的点，考察边(v5,v6),(v5,v7)的端点v6,v7。T(v6)=minT(v6),P(v5)+l56=min8,7+1=8T(v7)=minT(v7),P(v5)+l57=min,7+7=1477(9) 比较所有T标号，T(v6)最小，所以令P(v6)=8v1(0)v2v7v5v411344452572(4)(4)(7)14(8)v3(2)v6(10) v6为刚得

32、到P标号的点，考察边(v6,v7)的端点v7。T(v7)=minT(v7),P(v6)+l67=min14,8+5=13v1(0)v2v7v5v411344452572(4)(4)(7)13(8)v3(2)v677(11) 只有一个T标号T(v7)，令P(v7) =13 ，停止。v1(0)v2v7v5v411344452572(4)(4)(7)(13)(8)v3(2)v67计算结果见上图，v1到v7的最短路为：76431vvvvv765431vvvvvv同时得到v1到其余各点的最短路* 这个算法只适用于全部权为非负情况如果某边的权为负，算法失效。上面的例题是针对无向图求最短路的问题，对有向图最

33、短路的求法类似。下面以设备更新问题为例说明有向图最短路的计算方法。例(设备更新问题)某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：年份1234年初购价10111213维修费用24714问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。符号的含义：vi第i年年初购进一台新设备(v5表示第四年年底)弧(vi,vj)表示第i年年初购

34、进的设备一直使用到第j年年初(即第j-1年年底)弧(vi ,vj)的权数表示从第i年年初购进的设备一直使用到第j年年初所花费的购置费和维修费用的总和。如何制定使得总费用最少的设备更新计划问题可以转化最短路问题。此最短路问题如图所示。图中权数ij的确定：12=10+2=12；13=10+2+4=16；14=10+2+4+7=23；15=10+2+4+7+14=37；23=11+2=13；24=11+2+4=17；25=11+2+4+7=24；34=12+2=14；35=12+2+4=18；45=13+2=15下面用Dijkstra算法求v1到v5的最短路。给v1以P标号，P(v1)=0, 其余各

35、点给以T标号，T(vi)= +(1) (i=2,3,4,5)。（图中( )内的数表示P标号； 内的数表示T标号）(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）A，且v2,v3, v4,v5为T标号，所以修改这四个点的标号： T(v2) =min T(v2), P(v1)+ 12= min +, 0+12=12T(v3) =min T(v3), P(v1)+ 13= min +, 0+16=16T(v4) =min T(v4), P(v1)+ 14= min +, 0+23=23T(v5) =min T(v5), P(v1)+ 15= min +, 0+37=37(3)

36、 比较所有具有T标号的点，把最小者改为P标号。T(v2)最小，令P(v2)=12。 (4) v2为刚得到P标号的点，考察弧(v2,v3),(v2,v4), (v2,v5)的端点v3,v4,v5。T(v3) =min T(v3), P(v2)+ 23= min 16, 12+13=16T(v4) =min T(v4), P(v2)+ 24= min 23, 12+17=23T(v5) =min T(v5), P(v2)+ 25= min 37, 12+24=36(5) 比较所有具有T标号的点，把最小者改为P标号。T(v3)最小，令P(v3)=16。 (6)考察点v3 T(v4) =min T(v

37、4), P(v3)+ 34= min23, 16+14=23 T(v5) =min T(v5), P(v3)+ 35= min36, 16+18=34(7) 所有T标号中，T(v4)最小，令P(v4)=23(8)考察点v4 T(v5) =min T(v5), P(v4)+ 45= min34, 23+15=34(9)只有一个T标号T(v5)，令P(v5)=34，计算结束。 由上可知：v1到v5的最短路为v1v3v5,长度为34。其含义为：最佳更新计划为第一年年初购买新设备使用到第二年年底(第三年年初)，第三年年初再购买新设备使用到第四年年底，这个计划使得总的支付最小，其值为34。v1v3v2v

38、7v5v4v617134452572练习、求下图中任意两点间的最短路40575014771034430215720241045240)0(DD例、某地7个村庄之间的现有交通道路如下图所示，边旁数字为各村庄之间道路的长度。现要在某一村庄修建一所小学，该小学应建在哪个村庄,可使离该村最远的村庄的学生所走的路程最少？7634422571243v1v2v3v4v5v6v7村庄间的道路交通图该问题可分作两步来考虑：1）求出任意两个村庄之间的最短路长；2）找出每一点到其余各点按照最短路线的最远点,大中取小即可。首先写出权矩阵024620174102546202775034423037430)0(D用Flo

39、yd算法求出任意两点之间的最短路的长度023587102013658310254753205258655034754230310875430)7(D找出每一点到其余各点按照最短路线的最远点取这些最远距离中的最小者(小学应建在v4村)108758710max作业: P227 习题4.4最大流问题最大流问题是在一个给定网络上求流量最大的可行流，即给一个网络的每条弧规定一个流量的上界，求从点vs到vt的最大流。下图是一个输油管道网，vs为起点，vt为终点，v1v6为中转站，弧旁的数表示该管道的最大输油量。问题：如何安排，才能使从vs到vt的输油量最大？oooooooovsvtv1v2v3v5v6v4

40、4267434232211|最大流问题|1最大流问题的数学描述|1 .1网络中的流定义 在以V 为节点集， A为弧集的有向图G = (V, A)上定义如下的权函数：|（i）L : A R 为孤上的权函数，弧(i, j) A对应的权L(i, j)记为 l ij ，称为孤(i, j)的容量下界（lower bound）；|（ii）U : A R 为弧上的权函数，弧(i, j) A对应的权U(i, j)记为u ij ，称为孤(i, j)的容量上界，或直接称为容量（capacity）；|（iii）D :V R为顶点上的权函数，节点iV 对应的权D(i)记为d i ，称为顶点i 的供需量（supplyd

41、emand）；此时所构成的网络称为流网络，可以记为N = (V, A, L,U,D)。|由于我们只讨论V, A为有限集合的情况，所以对于弧上的权函数L,U 和顶点上的权函数D ，可以直接用所有孤上对应的权和顶点上的权组成的有限维向量表示，因此L,U,D 有时直接称为权向量，或简称权。|由于给定有向图G = (V, A)后，我们总是可以在它的弧集合和顶点集合上定义各种权函数，所以流网络一般也直接简称为网络。|定义 对于流网络N = (V, A,L,U,D)，其上的一个流（flow） f 是指从N 的弧集A到R 的一个函数，即对每条弧(i, j)赋予一个实数f ij （称为弧(i, j)的流量）。

42、如果流 f 满足 则称 f 为可行流（feasible flow）。至少存在一个可行流的流网络称为可行网络（feasible network）约束（1）称为流量守恒条件（也称流量平衡条件），约束（2）称为容量约束。 定义： 设有向连通图G(V,E)，G的每条边(vi,vj)上有非负数cij称为边的容量，仅有一个入次为0的点vs称为发点(源)，一个出次为0的点vt称为收点(汇)，其余点为中间点，这样的网络G称为容量网络，常记做G(V,E,C)。 对任一G中的边(vi,vj)有流量fij,，称集合ffij网络G上的一个流。称满足下列条件的流f为可行流： (1)容量限制条件：对G中每条边(vi,vj

43、)，有0fijcij (2)平衡条件：对中间点vi， (即中间点vi的物资的输入量与输出量相等) 对收、发点vs,vt,有 (即从vs点发出的物资总量等于vt点输入的量。)W为网络流的总流量。 kkijijffWffjjtisi可行流总是存在的，例如f0就是一个流量为0的可行流。最大流问题就是在容量网络中，寻找流量最大的可行流。 一个流f=fij,当fij=cij，则称流f对边(vi,vj)是饱和的，否则称f对(vi,vj)不饱和。根据弧的流量是否为0，可把弧分为零流弧和非零流弧两类。 最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。把网络D=(V,E,C)的点

44、集V剖分为两个非空集合Vs和Vt(即VsVt=，VsVt=V)，使vsVs, vtVt，把从Vs指向Vt的弧的全体称为（分离vs和vt的）截集。称截集中所有弧的容量之和为这个截集的容量（简称为截量）。分离vs和vt的截集往往不只一个，称其中截量最小的为最小截集。 由截集的定义可知：截集是从vs到vt的必经之路，无论去掉哪个截集，从vs到vt就不存在路了，因此任何一个可行流的流量不会超过任何一个截集的容量。因而若能找到一个可行流和一个截集，使得可行流的流量等于这个截集的容量，则该可行流一定是最大流，该截集一定是最小截集。 在上图中，若令Vs=vs,v1,v6,Vt=v2,v3,v4,v5, vt

45、,则：截集为(vs,v5)(v1,v2),(v1,v5), (v6,v5) ,(v6,v4),截量为3+2+4+2+3=14；oooooooovsvtv1v2v3v5v6v44267434232211设是网络中从vs到vt的一条链，给定向为从vs到vt，沿此方向上的弧可分为两类：一类是与链的方向一致的弧称为正向弧，用+ 表示正向弧的全体，另一类是与链的方向相反的弧称为反向弧，用- 表示反向弧的全体。在上图中，在链=vs,v5,v6,v4,v3,vt中，+=(vs,v5),(v6,v4),( v3,vt),-=(v5,v6),(v4,v3)。增广链：对于可行流f，是一条从vs到vt的一条链，如果

46、+中的弧均为非饱和弧，-中的弧均为非零流弧，则称为从vs到vt的关于f 的增广链。定理（最大流量最小截量定理）：在网络N中，从vs到vt的最大流的流量等于分离vs到vt的最小截集的截量。计算网络最大流的方法增广链的实际意义在于沿着这条链存在增大输送能力的潜力。如沿着增广链1=vs,v2,v5,v4,v6,vt，凡是正向弧的流量都增加1，反向弧的流量都减少1（见上图），结果整个网络的流增加了1，即由6增加到7。用这种方法调整后的流仍为可行流。这样就得到了一个寻找最大流的方法：从一个可行流开始，寻找关于这个可行流的增广链，若增广链存在，则可以经过调整，得到一个新的可行流，其流量比调整前的可行流大，

47、重复这个过程，直到不存在增广链时就得到了最大流。下面介绍计算网络最大流的标号算法标号法是由 Ford 和Fulkerson 在1957 年提出的设已有一个可行流f(若网络中没有给出可行流,则可设f为零流)，标号法可分为两步：（一）标号过程在这个过程中,网络中的点或者是标号点，或者是未标号点。每个标号点的标号包含两个部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。(1) 给发点vs以标号（0，+），第二个数值表示从上一标号点到这个标号点的最大允许调整量。vs为发点，不限允许调整量，故为+。最大流的一种算法标号法(2) 选择一个已标号的点vi,对

48、于vi的所有未标号的邻点vj,按下列规则处理：若边(vi,vj) E,且fij0,则令vj=minfji, vi,并给vj以标号(-vi,vj)(3) 重复(2)直到收点vt被标号或不再有点可标号时为止。 若vt得到标号，说明存在一条增广链，转(二)调整过程。若vt未得到标号，标号过程已无法进行时，说明f已是最大流。（二）调整过程 (1) 确定调整量=vt， (2) 若vt的标号为（vj, vt）,则以fit+代替fit; 若vt的标号为 （- vj , vt）,则以fit-代替fit。 (3) 令vj代替vt，返回(2)；若vj=vs，则去掉所有标号转(一)。|。用标号法寻求网络中最大流的基

49、本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。|A.标号过程：通过标号过程寻找一条可增广轨。|B.增流过程：沿着可增广轨增加网络的流量。|这两个过程的步骤分述如下例、用标号法求下图所示的网络中从vs到vt的最大流量，图中弧旁数值为容量cij (1) 图中没有给出初始可行流,可设零流为出初始可行流.如图1。先给vs标以标号

50、（0，+）。(2) 检查vs的邻点v1,v2可知（vs,v1）E，且fs1=0cs1=10,令v1=min +,10-0 =10,给v1以标号（vs,10）。用同样的方法给v2以标号（vs,14）。见图2(3) 检查v1的尚未标号的邻点v3,v4可知(v1,v3)E，且f13=0c13=10,令v3=minv1, 10-0=min10,10=10,给v3以标号(v1,10), 用同样的方法给v4以标号(v1,10)。(4) 检查v3的尚未标号的邻点v5,v6可知(v3,v5）E，且f35=0c35=4,令v5=minv3, 4-0=min10,4=4,给v5以标号(v3,4), 对于v6，由于

51、(v6,v3)E，且f63=0，不满足标号条件。检查v4的尚未标号的邻点vt可知(v4,vt)E，且f4t=0c4t=13,令vt=minv4, 13-0=min10,13=10,给vt以标号(v4,10)。(5)由于vt已得到标号，则存在增广链，标号过程结束，转入调整过程。令=vt=10为调整量，从vt开始，按标号(v4,10)找到v4并用f4t+10代替f4t，由标号(v1,10)找到v1并用f14+10代替f14，再由标号(vs,10)找到vs并用fs1+10代替fs1，调整过程结束。调整后的可行流见图5。去掉所有标号，重新开始标号过程。图 5先给vs标以标号（0，+）。检查vs的邻点v

52、1,v2可知（vs,v1）E但fs1=10=cs1=10, 不满足标号条件。（vs,v2）E且fs2=0|M|(|M|表示集合M中边的条数)，则称M为最大匹配。上例中的问题用图的语言描述如下：用x1,x2,xn表示n个工人，y1,y2,ym表示m项工作，(xi,yj)表示工人xi能胜任工作yj。X=x1,x2,xn，Y=y1,y2,ym，得到一个二部图G=(X,Y,E)。问题：在图G中找一个边集E的子集M，使得M中的任意两条边没有公共端点，并且边数尽可能的多，即最大匹配。.x1x2x3xny1y2y3ym令M) j , i (0M) j , i (1xij若边若边则最大匹配问题的线性规划模型为

53、：E) j , i (10 xVi, 1x. t . sxmaxijE) j , i (ijE) j , i (ijij变量，为这里ij=1二、最优匹配例4.15、现有4个工人，4台不同的机床，由于工人对各台机床的操作技术水平不同，每个工人在各台机床上完成给定任务所需工时不同，其效率矩阵为：问题：哪个工人操作哪台机床可使总工时最少？1351015151094927917131114W工 人机 床min z=s.t.n1in1jijijx10 xn,.,2,1j1xn,.,2,1i1xijn1iijn1jij或(2)匈牙利方法定理4.9：若矩阵W的元素可分成0与非0两部分，则覆盖0元素的直线数等

54、于位于不同行不同列的0元素的最大个数。 定理4.8： 如果从分配问题效率矩阵W=(ij) 的每一行元素中分别减去(或加上)一个常数ui，从每一列分别减去(或加上)一个常数vj ，得到一个新效率矩阵B=(bij),其中bij= ij-ui-vj,则二者的最优解等价。匈牙利方法：根据定理4.8的方法不断变换效率矩阵W，使其产生尽可能多的0元素，并且始终保持所有元素非负，直到能从变换后的矩阵中找出位于不同行不同列的0元素为止，这些0元对应的xij=1,其余元素对应xij=0的方案为最优解。下面以例4.15说明最优匹配的匈牙利方法的应用542111351015151094927917131114W80

55、51011650705762036000205105650105702031B1、变换效率矩阵2、在B1中寻找位于不同行、不同列的0元20510565010570203*1B1)检查B1的每行(列)，从中找出未加标记的0元最少的行(列)，在该行(列)用*标出一个0元，若该行(列)有多个0元,则任意标一个。2)把刚得到的0*所在的行、列中的其余0元划去，用0表示。3)0*、0就是有标记的0元，返1).反复进行,直到所有0元都有标记为止。这样得到的0*元一定位于不同行、不同列。如果个数等于n,已符合最优性条件,否则转33、找出能覆盖矩阵中所有0元的最少直线集合1)对没有0*的行打；2)对已打的行中

56、所有0元所在的列打；3)再对打有的列中所有0*元所在的行打；4)重复2),3)直到得不出新的打的行、列为止；5)没有打的行和打的列就是覆盖所有0元的最少直线集合。20510565010570203*1B4、修改矩阵B11)在未被直线覆盖的所有元素中找出最小元素；2)所有打的行都减去此最小元素，所有打的列都加上此最小元素。令这个新矩阵为B2，返回2。205105650105702031B10495750004603032B10495750004603032B*符合最优条件，总工时29x1x2x3x4y1y2y3y411945工人机床一般的指派问题在实际应用中，会遇到各种非标准形式的指派问题。通常

57、的处理方法是先将它们转化为标准形式，然后再用匈牙利法求解1、最大化指派问题设最大化指派问题系数矩阵C(cij)nn。其中最大元素为m。令矩阵B(bij)nn=(m-cij)nn。则以B为系数矩阵的最小化指派问题和以C为系数矩阵的原最大化指派问题有相同最优解。9118713161491514210413152C7589302712126123114916111681671613161616141691615161416216101641613161516216B例 矩阵的最大元素为c33=16,取m=16,令2人数和事数不等的指派问题若人少事多，则添上一些虚拟的“人”。这些虚拟的“人”做各事的费

58、用系数可取0、理解为这些费用实际上不会发生。若人多事少，则添上一些虚拟的“事”。这些虚拟的“事”被各人做的费用系数同样也取0。3一个人可做几件事的指派问题若某个人可做几件事，则可将该人化作相同的几个“人”来接受指派。这几个“人做同一件事的费用系数当然都一样。4某事一定不能由某人做的指派问题若某事一定不能由某个人做，则可将相应的费用系数取作足够大的数M。例、 某商业公司计划开办五家新商店。为了尽早建成营业：商业公司决定由5家建筑公司分别承建。已知建筑公司Ai(i1,2, ,5)对新商店Bj(j1,2,5)的建造费用的报价(万元)为cij(i，j1,2,5)，见下表。商业公司应当对5家建筑公司怎样

59、分配建造任务，才能使总的建造费用最少?BjB1B2B3B4B5AiA14871512A279171410A3691287A46714610A56912106cij这是标准形式的指派问题为了保证工程质量，经研究决定舍弃建筑公司A1和A5，而让技术力量较强的建筑公司A1、A2和A3来承建。根据实际情况，可以允许每家建筑公司承建一家或二家商店。求使总费用最少的指派方案。反映投标费用的系数矩阵为：BjB1B2B3B4B5AiA14871512A279171410A3691287cij由于每家建筑公司最多可承建两家新商店，因此，把每家建筑公司化作相同的两家建筑公司(Ai 和 ，i1，2，3)。这样，系数

60、矩阵变为： 78129678129610141797101417971215784121578454321BBBBB332211AAAAAAiA上面的系数矩阵有6行5列，为了使“人”和“事”的数目相同，引入一件虚工作B6，使之成为标准指派问题的系数矩阵：078129607812960101417970101417970121578401215784654321BBBBBB332211AAAAAA用匈牙利解法解以C为系数矩阵的最小化指派问题，得最优指派方案为由A1承建B1和B3,A2承建B2，A3承建B4和B5。这样，总的建造费用最省，为4十7十9十8十735(万元)。工作数量工人数量工作的数量