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

图与网络模型及方法|图与子图|图的连通与割集|树与支撑树|最小树|最短有向路|最大流|最小费用流|最大对集绪论|图论中所谓的“图”是指某类具体事物和这些事物之间的联系。|如果我们用点表示这些具体事物，用连接两点的线段（直的或曲的）表示两个事物的特定的联系，就得到了描述这个“图”的几何形象。|图论为任何一个包含了一种二元关系的离散系统提供了一个数学模型，借助于图论的概念、理论和方法，可以对该模型求解。哥尼斯堡七桥问题这个图是连通的，且每个点都与偶数线相关联这个图是连通的，且每个点都与偶数线相关联绪论|图与网络是运筹学（OperationsResearch）中的一个经典和重要的分支，所研究的问题涉及经济管理、工业工程、交通运输、计算机科学与信息技术、通讯与网络技术等诸多领域|的最短路问题、最大流问题、最小费用流问题和匹配问题等都是图与网络的基本问题。图-由若干个点和连接这些点的连线所组成的图形vi图中的点，称为顶点（代表具体事物，研究对象。ei图中的连线，称为边（对象之间的联系）m(G)=|E|G的边数，简记为mn(G)=|V|G的顶点数，简记为n一.图的概念记V=vi点的集合，E=ei边的集合G=V，EG 一个图m=6,n=5图的基本概念有向图无向图边e=(vi,vj)有方向vi为始点，vj为终点边e=(vi,vj)无方向，此时(vi,vj)=(vj,vi)e4=(v3，v4）=(v4，v3）e4=(v3，v4)(v4，v3）e5=(v3，v4）=(v4，v3）此时(vi,vj)(vj,vi)e5=(v4，v3)(v3，v4)图有向图无向图二.常用名词：1、端点和关联边：2、相邻点和相邻边：3、多重边与环：4、多重图和简单图：无环也无多重边的图称为简单图。含有多重边的图称为多重图；5、次：6、悬挂点和悬挂边：次为1的点称为悬挂点，与悬挂点相联的边称为悬挂边。7、孤立点：8、奇点与偶点：，G的边数m=6性质性质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)均为偶数，所以只有偶数个奇数相加才能得到偶数，所以V1中的点，即奇点的个数为偶数。四四.链、路、连通图链、路、连通图1.链：对于无向图G=(V，E)，若图G中有一个点与边的交替序列=vi0,ei1,vi1,ei2,vik-1,eik,vik，且eit=(vit-1,vit)(t=1,2,k),则称该交替序列为连结vi0和vik的一条链。简单链：简单链：中只有重复的点而无重复边者为简单链。初等链：初等链：中没有重复的点和重复边者为初等链。圈：圈：无向图G中，连结vi0与vik的一条链，当vi0与vik是同一个点时，称此链为圈。圈中只有重复点而无重复边者为简单圈，既（除起点、终点重复外）无重复点也无重复边者为初等圈不是链初等链简单链（简单圈）（初等圈）2 路路：在有向图D=(V，A)中，若有从vi0到vik不考虑方向的链，且各边方向一致，则称之为从vi0到vik的一条路。对于有向图可以类似于无向图定义链和圈，初等链、圈，简单链、圈此时不考虑边的方向。而当链(圈)上的边方向相同时，称为道路(回路)。对于无向图来说，道路与链、回路与圈意义相同3 连通图连通图：一个图中任意两点间至少有一条链(或路)相连的图。连通图非连通图五网络在实际问题中，往往只用图来描述所研究对象之间的关系还不够，与图联系在起的，通常还有与点或边有关的某些数量指标，通常称之为“权”，权可以代表如距离、费用、通过能力(容量)等等。这种带有某种数量指标的图称为网络(赋权图)。如公路交通图：vi表示城市,ei表示公路w(ei)表示公路ei的长度如w(e2)=50表示城市v2与城市v3之间的距离是50千米六.完全图、偶图1完全图：一个简单图，若任意两个顶点之间均有一条边相连，则称这样的图为完全图。对于完全图，由于每个顶点与所有其余顶点都有一条边相连，所以在有n个顶点的完全图中，各个顶点的次均为（n-1）。2.偶图：若图G的顶点能分成两个互不相交的非空集合V1和V2，使在同一集合中的任意两个顶点均不相邻，称这样的图为偶图，也称为二部图。若偶图的顶点集合V1，V2之间的每一对不同顶点都有一条边相连，称这样的图为完全偶图。v2v3v4v5v2v3v4v5v1v1完全图(完全)偶图定理定理 一个图为偶图的充分必要条件该图无奇圈一个图为偶图的充分必要条件该图无奇圈七.子图、部分图对于图G1=V1,E1和图G2=V2,E2,若有，称G1是G2的一个子图。若有，称G1是G2的一个部分图（生成子图）。*部分图也是子图，但子图不一定是部分图。生成子图七.子图、部分图*部分图也是子图，但子图不一定是部分图。生成子图对于图G1=V1,E1和图G2=V2,E2,若有，称G1是G2的一个子图。若有，称G1是G2的一个部分图（生成子图）。八.前向弧与后向弧设是一条从vs到vt的链，则链上与链的方向一致的弧称为前向弧，记这些弧为+；链上与链的方向相反的弧称为后向弧，记这些弧为-。vsv1v2v3v4v5vt前向弧与后向弧|子图子图 设设 G1=V1,E1,G2=V2,E2子图定义：子图定义：如果V2V1,E2E1称G2是G1的子图；真子图：真子图：如果V2V1,E2E1称G2是G1的真子图；部分图：部分图：如果V2=V1,E2E1称G2是G1的部分图；导出子图：导出子图：如果V2V1,E2=vi,vjvi,vjV2，称G2是G1中由V2导出的导出子图。九、图的矩阵表示 用矩阵表示图对研究图的性质及应用常常是比较方便的定义：网络(赋权图)G(V，E)，其边(vi,vj)有权ij,构造矩阵A=(aij)nn,其中：称矩阵A为网络G的权矩阵。例、写出下图的权矩阵v1v2v3v4v5765424938定义：对于图G(V，E)，|V|=n,构造一个矩阵A=(aij)nn,其中：称矩阵A为图G的邻接矩阵。例、写出下图的邻接矩阵v1v3v5v2v4v6当G为无向图时，邻接矩阵为对称矩阵最短轨道问题最短轨道问题|给出了一个连接若干个城镇的铁路网络，在这个给出了一个连接若干个城镇的铁路网络，在这个网络的两个指定城镇间，找一条最短铁路线。网络的两个指定城镇间，找一条最短铁路线。|以各城镇为图以各城镇为图G 的顶点，两城镇间的直通铁路为的顶点，两城镇间的直通铁路为图图G 相应两顶点间的边，得图相应两顶点间的边，得图G。对。对G 的每一边的每一边e，赋以一个实数，赋以一个实数w(e)直通铁路的长度，称为直通铁路的长度，称为e的的权，得到赋权图权，得到赋权图G。G 的子图的权是指子图的各的子图的权是指子图的各边的权和。边的权和。|问题就是求赋权图问题就是求赋权图G 中指定的两个顶点中指定的两个顶点u0,v0间的间的具最小权的轨。这条轨叫做具最小权的轨。这条轨叫做u0,v0间的最短路，它间的最短路，它的权叫做的权叫做u0,v0间的距离，亦记作间的距离，亦记作d(u0,v0)最短轨道问题求法最短轨道问题求法 -Dijkstra算法|基本思想是按距u 0从近到远为顺序，依次求得u 0到G 的各顶点的最短路和距离，直至v 0（或直至G 的所有顶点），算法结束。为避免重复并保留每一步的计算信息，采用了标号算法。最短轨道问题求法最短轨道问题求法 -Dijkstra算法定义：连通且不含圈的无向图称为树。记作T(V，E)二、二、树树|树可以有很多等价的定义,以下定理中的各命题都体现树的特征.定理设G=V,E是一无向图，|V|=n，|E|=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)图的生成树最小生成树的求法：避圈法与破圈法定义：树的各条边称为树枝。一般图G的生成树有多个，称其中树枝总长度最小的生成树为最小树。避圈法：在图G中，每步选出一条边e，使它与已选边不构成圈，且e是未选边中长度最小的边，直到选够n-1边为止。v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232v1v2v3v8v7v6v5v4v04112131444523552v1v2v3v8v7v6v5v4v011211232破圈法：从网络图N中任取一回路，去掉该回路中权数最大的一条边，得一子网络图N1。在N1中再任取一回路，去掉该回路中权数最大的一条边，得一子网络图N2。如此继续下去，直到剩下的子图中不再含回路为止。该子图就是N的最小生成树。v1v2v3v8v7v6v5v4v04112131444523552筑路选线问题|欲修筑连接n个城市的铁路，已知i城与j城之间的铁路造价为wij，设计一个线路图使总造价最低|连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具最小权的生成树叫做最小生成树|造最小生成树的两种常用算法-prim 算法与Kruskal 算法。prim 算法构造最小生成树|设置两个集合P 和Q,其中P 用于存放G 的最小生成树中的顶点，集合Q存放G的最小生成树中的边。令集合P的初值为1P=v（假设构造最小生成树时，从顶点v 1出发），集合Q的初值为Q=。|prim算法的思想是：从所有pP，vV P的边中，选取具有最小权值的边pv，将顶点v 加入集合P 中，将边pv 加入集合Q中，如此不断重复，直到P=V 时，最小生成树构造完毕，这时集合Q中包含了最小生成树的所有边。Kruskal 算法构造最小生成树可行遍问题|定义1：经过G 的每条边的迹叫做G 的Euler迹；闭的Euler迹叫做Euler回路或E回路；含Euler回路的图叫做Euler图。|直观地讲，Euler图就是从一顶点出发每边恰通过一次能回到出发点的那种图，即不重复地行遍所有的边再回到出发点。|定理6（i）G 是Euler图的充分必要条件是G 连通且每顶点皆偶次。|（ii）G 是Euler图的充分必要条件是G 连通且|（iii）G 中有Euler迹的充要条件是G 连通且至多有两个奇次点。|定义包含G 的每个顶点的轨叫做Hamilton(哈密顿)轨；闭的Hamilton轨叫做Hamilton圈或H 圈；含Hamilton圈的图叫做Hamilton图。|直观地讲，Hamilton图就是从一顶点出发每顶点恰通过一次能回到出发点的那种图，即不重复地行遍所有的顶点再回到出发点。Euler回路的Fleury算法可行遍问题的应用|中国邮递员问题一位邮递员从邮局选好邮件去投递，然后返回邮局，当然他必须经过他负责投递的每条街道至少一次，为他设计一条投递路线，使得他行程最短。|中国邮递员问题的数学模型：在一个赋权连通图上求一个含所有边的回路，且使此回路的权最小。|若此连通赋权图是Euler图，则可用Fleury算法求Euler回路，此回路即为所求。|对于非Euler图，1973年，Edmonds和Johnson给出下面的解法：多邮递员问题|邮局有k(k 2)位投递员，同时投递信件，全城街道都要投递，完成任务返回邮局，如何分配投递路线，使得完成投递任务的时间最早？我们把这一问题记成kPP。|kPP的数学模型如下：旅行商（TSP）问题|一名推销员准备前往若干城市推销产品，然后回到他的出发地。如何为他设计一条最短的旅行路线（从驻地出发，经过每个城市恰好一次，最后返回驻地）？|是在一个赋权完全图中，找出一个有最小权的Hamilton圈。称这种圈为最优圈|与最短路问题及连线问题相反，目前还没有求解与最短路问题及连线问题相反，目前还没有求解旅行商问题的有效算法。所以希望有一个方法以旅行商问题的有效算法。所以希望有一个方法以获得相当好（但不一定最优）的解。获得相当好（但不一定最优）的解。改良圈算法。旅行商问题的数学表达式对集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 次（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，当且仅当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）。最优分派问题|在人员分派问题中，工作人员适合做的各项工作当中，效益未必一致，我们需要制定一个分派方案，使公司总效益最大。|这个问题的数学模型是：在人员分派问题的模型中，图G 的每边加了权|w(x i，y j)0表示 x i干 y j工作的效益，求加权图G 上的权最大的完美对集。|解决这个问题可以用库恩曼克莱斯（Kuhn-Munkres）算法|定义若映射l:V(G)R，满足xX,yY，l(x)+l(y)w(x,y)，|则称l 是二分图G 的可行顶点标号。|令El=xy|xy E(G),l(x)+l(y)=w(xy)，称以l E 为边集的G 的生成子图为相等子图，记作G l。|可行顶点标号是存在的。例如定理5 G l的完美对集即为G 的权最大的完美对集。Kuhn-Munkres 算法最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题可以便用这个模型如设备更新、管道铺设、线路安排、厂区布局等。最短路问题的一般提法：设G=V，E为连通图，图中各边(vi,vj)有权lij(lij=表示vi,vj间无边)。vs,vt为图中任意两点，求一条路，使它是从vs到vt的所有路中总权最小的路。即最小有些最短路问题是求网络中某指定点到其余所有点的最短路，或求网络中任意两点间的最短路。下面介绍三种算法，可分别用于求解这几种最短路问题。(2)(2)使用条件网络中所有的弧(边)权均非负非负，即：(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的估计最短路权的上界，是一种临时标号凡没有得到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(vj)=+,当存在两个以上最小者时，可同时改为P标号。若全部点均为P标号则停止。否则用代vi转回第二步。例、用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标号，所以修改这三个点的标号：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)=minT(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标号，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为刚得到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的最短路为：同时得到v1到其余各点的最短路*这个算法只适用于全部权为非负情况如果某边的权为负，算法失效。上面的例题是针对无向图求最短路的问题，对有向图最短路的求法类似。下面以设备更新问题为例说明有向图最短路的计算方法。例(设备更新问题)某企业在四年内都要使用某种设备，在每年年初作出是购买新设备还是继续使用旧设备的决策。若购买新设备就要支付购置费；若继续使用旧设备，则需支付维修费用。这种设备在四年之内每年年初的价格以及使用不同时间（年）的设备的维修费用估计为：年份1234年初购价10111213维修费用24714问题：制定一个四年之内的设备更新计划，使得四年之内的设备购置费和维修费用之和最小。可以用求最短路问题的方法来解决总费用最少的设备更新计划问题。符号的含义：vi第i年年初购进一台新设备(v5表示第四年年底)弧(vi,vj)表示第i年年初购进的设备一直使用到第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的最短路。(1)给v1以P标号，P(v1)=0,其余各点给以T标号，T(vi)=+(2)(i=2,3,4,5)。（图中()内的数表示P标号；内的数表示T标号）(2)由于（v1,v2）,(v1,v3),（v1,v4）,（v1,v5）A，且v2,v3,v4,v5为T标号，所以修改这四个点的标号：T(v2)=minT(v2),P(v1)+12=min+,0+12=12T(v3)=minT(v3),P(v1)+13=min+,0+16=16T(v4)=minT(v4),P(v1)+14=min+,0+23=23T(v5)=minT(v5),P(v1)+15=min+,0+37=37(3)比较所有具有T标号的点，把最小者改为P标号。T(v2)最小，令P(v2)=12。(4)v2为刚得到P标号的点，考察弧(v2,v3),(v2,v4),(v2,v5)的端点v3,v4,v5。T(v3)=minT(v3),P(v2)+23=min16,12+13=16T(v4)=minT(v4),P(v2)+24=min23,12+17=23T(v5)=minT(v5),P(v2)+25=min37,12+24=36(5)比较所有具有T标号的点，把最小者改为P标号。T(v3)最小，令P(v3)=16。(6)考察点v3T(v4)=minT(v4),P(v3)+34=min23,16+14=23T(v5)=minT(v5),P(v3)+35=min36,16+18=34(7)所有T标号中，T(v4)最小，令P(v4)=23(8)考察点v4T(v5)=minT(v5),P(v4)+45=min34,23+15=34(9)只有一个T标号T(v5)，令P(v5)=34，计算结束。由上可知：v1到v5的最短路为v1v3v5,长度为34。其含义为：最佳更新计划为第一年年初购买新设备使用到第二年年底(第三年年初)，第三年年初再购买新设备使用到第四年年底，这个计划使得总的支付最小，其值为34。v1v3v2v7v5v4v617134452572练习、求下图中任意两点间的最短路4例、某地7个村庄之间的现有交通道路如下图所示，边旁数字为各村庄之间道路的长度。现要在某一村庄修建一所小学，该小学应建在哪个村庄,可使离该村最远的村庄的学生所走的路程最少？该问题可分作两步来考虑：1）求出任意两个村庄之间的最短路长；2）找出每一点到其余各点按照最短路线的最远点,大中取小即可。首先写出权矩阵用Floyd算法求出任意两点之间的最短路的长度找出每一点到其余各点按照最短路线的最远点取这些最远距离中的最小者(小学应建在v4村)max作业:P227习题4.4覆盖与点独立集最大流问题最大流问题是在一个给定网络上求流量最大的可行流，即给一个网络的每条弧规定一个流量的上界，求从点vs到vt的最大流。下图是一个输油管道网，vs为起点，vt为终点，v1v6为中转站，弧旁的数表示该管道的最大输油量。问题：如何安排，才能使从vs到vt的输油量最大？|最大流问题|1最大流问题的数学描述|1.1网络中的流定义在以V 为节点集，A为弧集的有向图G=(V,A)上定义如下的权函数：|（i）L:AR 为孤上的权函数，弧(i,j)A对应的权L(i,j)记为 l ij，称为孤(i,j)的容量下界（lowerbound）；|（ii）U:AR 为弧上的权函数，弧(i,j)A对应的权U(i,j)记为u ij，称为孤(i,j)的容量上界，或直接称为容量（capacity）；|（iii）D:V R为顶点上的权函数，节点iV 对应的权D(i)记为d i，称为顶点i 的供需量（supplydemand）；此时所构成的网络称为流网络，可以记为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)的流量）。如果流f 满足则称f 为可行流（feasibleflow）。至少存在一个可行流的流网络称为可行网络（feasiblenetwork）约束（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)，有0fijcij(2)平衡条件：对中间点vi，(即中间点vi的物资的输入量与输出量相等)对收、发点vs,vt,有(即从vs点发出的物资总量等于vt点输入的量。)W为网络流的总流量。可行流总是存在的，例如f0就是一个流量为0的可行流。最大流问题就是在容量网络中，寻找流量最大的可行流。一个流f=fij,当fij=cij，则称流f对边(vi,vj)是饱和的，否则称f对(vi,vj)不饱和。根据弧的流量是否为0，可把弧分为零流弧和非零流弧两类。最大流问题实际是个线性规划问题，但是利用它与图的紧密关系，能更为直观简便地求解。把网络D=(V,E,C)的点集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,则：截集为(vs,v5)(v1,v2),(v1,v5),(v6,v5),(v6,v4),截量为3+2+4+2+3=14；设是网络中从vs到vt的一条链，给定向为从vs到vt，沿此方向上的弧可分为两类：一类是与链的方向一致的弧称为正向弧，用+表示正向弧的全体，另一类是与链的方向相反的弧称为反向弧，用-表示反向弧的全体。在上图中，在链=vs,v5,v6,v4,v3,vt中，+=(vs,v5),(v6,v4),(v3,vt),-=(v5,v6),(v4,v3)。增广链：对于可行流f，是一条从vs到vt的一条链，如果+中的弧均为非饱和弧，-中的弧均为非零流弧，则称为从vs到vt的关于f的增广链。定理（最大流量最小截量定理）：在网络N中，从vs到vt的最大流的流量等于分离vs到vt的最小截集的截量。计算网络最大流的方法增广链的实际意义在于沿着这条链存在增大输送能力的潜力。如沿着增广链1=vs,v2,v5,v4,v6,vt，凡是正向弧的流量都增加1，反向弧的流量都减少1（见上图），结果整个网络的流增加了1，即由6增加到7。用这种方法调整后的流仍为可行流。这样就得到了一个寻找最大流的方法：从一个可行流开始，寻找关于这个可行流的增广链，若增广链存在，则可以经过调整，得到一个新的可行流，其流量比调整前的可行流大，重复这个过程，直到不存在增广链时就得到了最大流。下面介绍计算网络最大流的标号算法标号法是由Ford和Fulkerson在1957年提出的设已有一个可行流f(若网络中没有给出可行流,则可设f为零流)，标号法可分为两步：（一）标号过程在这个过程中,网络中的点或者是标号点，或者是未标号点。每个标号点的标号包含两个部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。(1)给发点vs以标号（0，+），第二个数值表示从上一标号点到这个标号点的最大允许调整量。vs为发点，不限允许调整量，故为+。最大流的一种算法标号法(2)选择一个已标号的点vi,对于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，则去掉所有标号转(一)。标号法寻求网络中最大流的基本思想|。用标号法寻求网络中最大流的基本思想是寻找可增广轨，使网络的流量得到增加，直到最大为止。即首先给出一个初始流，这样的流是存在的，例如零流。如果存在关于它的可增广轨，那么调整该轨上每条弧上的流量，就可以得到新的流。对于新的流，如果仍存在可增广轨，则用同样的方法使流的值增大，继续这个过程，直到网络中不存在关于新得到流的可增广轨为止，则该流就是所求的最大流。标号法过程|A.标号过程：通过标号过程寻找一条可增广轨。|B.增流过程：沿着可增广轨增加网络的流量。|这两个过程的步骤分述如下例、用标号法求下图所示的网络中从vs到vt的最大流量，图中弧旁数值为容量cij(1)图中没有给出初始可行流,可设零流为出初始可行流.如图1。先给vs标以标号（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，由于(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的邻点v1,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中的任意两条边没有公共端点，并且边数尽可能的多，即最大匹配。令则最大匹配问题的线性规划模型为：这里ij=1二、最优匹配例4.15、现有4个工人，4台不同的机床，由于工人对各台机床的操作技术水平不同，每个工人在各台机床上完成给定任务所需工时不同，其效率矩阵为：问题：哪个工人操作哪台机床可使总工时最少？工人机床(1)(1)数学模型数学模型对于有对于有n n个工人和个工人和n n项工作的分配问题，社项工作的分配问题，社x xij ij=1=1或或0 0分别表示工人分别表示工人i i做做/不做不做工作工作j j，数学模型为：，数学模型为：minz=s.t.(2)匈牙利方法定理4.9：若矩阵W的元素可分成0与非0两部分，则覆盖0元素的直线数等于位于不同行不同列的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说明最优匹配的匈牙利方法的应用1、变换效率矩阵2、在B1中寻找位于不同行、不同列的0元1)检查B1的每行(列)，从中找出未加标记的0元最少的行(列)，在该行(列)用*标出一个0元，若该行(列)有多个0元,则任意标一个。2)把刚得到的0*所在的行、列中的其余0元划去，用0表示。3)0*、0就是有标记的0元，返1).反复进行,直到所有0元都有标记为止。这样得到的0*元一定位于不同行、不同列。如果个数等于n,已符合最优性条件,否则转33、找出能覆盖矩阵中所有0元的最少直线集合1)对没有0*的行打；2)对已打的行中所有0元所在的列打；3)再对打有的列中所有0*元所在的行打；4)重复2),3)直到得不出新的打的行、列为止；5)没有打的行和打的列就是覆盖所有0元的最少直线集合。4、