运筹学图与网络优化.pptx

网络规划概述网络规划(Network Programming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。第1页/共130页七桥问题七桥问题图形七桥问题图形第2页/共130页原 理 及 方 法 七桥问题是图论中的著名问题。七桥问题是图论中的著名问题。17361736年，年，EulerEuler巧妙巧妙地将此问题化为图的不重复一笔画问题，并证明地将此问题化为图的不重复一笔画问题，并证明了了该问题不存在肯定回答。原因在于该图形有顶点该问题不存在肯定回答。原因在于该图形有顶点连连接奇数条边。接奇数条边。第3页/共130页10.1 图的基本概念一个图(Graph)定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合记记 是关联函数第4页/共130页图的端点设G是一个图(Graph)G=(V(G),E(G)，则称e连接u和v，称u和v是e的端点。若称端点u，v与边e是关联的，称两个顶点u，v是邻接的。第5页/共130页设G是一个图，图10G的几何实现的几何实现第6页/共130页图的几何实现 一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。第7页/共130页说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。第8页/共130页几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图 中，它共有4个顶点，6条边；而e 3 与e 4 的交点不是这个图的顶点。第9页/共130页平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。第10页/共130页基本概念端点重合为一点的边称为环。连接同一对顶点的多条边称为多重边。在右图中，e5 是一个环，e1 与e2 是多重边，v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。第11页/共130页邻接矩阵设G是一个图，G=(V(G),E(G)，定义图G的邻接矩阵A(G)=(aij)为mm矩阵,aij是顶点vi与边vj相邻接的边数。其中第12页/共130页关联矩阵设G是一个图，G=(V(G),E(G)定义图G的关联矩阵M=(mij)为mn矩阵；其中mij是顶点vi与边ej相关联的次数，取值可能为0、1、2。第13页/共130页注图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。第14页/共130页顶点的度设G是一个图，G=(V(G),E(G)，定义图G的顶点v的度为与顶点v相关联的边数，记作d(v)例例称度为奇数的顶点为奇点；称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。第15页/共130页例2222 2224+3+3+4=14=27第16页/共130页关联矩阵性质图G的关联矩阵M=(mij)为mn矩阵；则每行元素之和等于相应顶点的度；每列元素之和等于2。因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。定理设G是一个图，则第17页/共130页推论图中奇点的数目为偶数。证明证明记记第18页/共130页简单图一个图称为简单图，如果它既没有环也没有多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为平凡图；边集是空集的图称为空图。第19页/共130页同构称G和H是同构的，记为，使得给定两个图如果存在两个一一对应第20页/共130页同构图例图G与图H是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4第21页/共130页完全图Kn完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.K5第22页/共130页二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y;(X,Y)也称为图的二分划。x1x2x3y1y2y3第23页/共130页完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中K3,3第24页/共130页特殊图例K5K 3,3都是极小的非平面图都是极小的非平面图第25页/共130页子图称图H是图G的子图，图G及其基本图称H是G的支撑子图支撑子图，如果称H是G的真子图，若如果表示关联函数记为在H的限制。第26页/共130页顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为GW。导出子图GV-w记为G-W，即 它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把 简记为。第27页/共130页边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为GF。记G-F表示以E(G)F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F=e，则记。第28页/共130页子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图的支撑子图G-e1,e 2,e 3第29页/共130页子图图例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2,v 5 v1v2v3v4e1e3e2G e1,e 2,e 3v1v2v3v4v5e1e3e2G第30页/共130页途径顶点vk叫W的终点，顶点v0 称为W的起点，顶点vi 叫W的内部顶点，整数k称为W的长度。在简单图中，径可由顶点序列表示。图G的一个有限的点边交错序列称为从v0到vk的途径。其中vi与vi+1是边ei的顶点;第31页/共130页路、链如果径W的边不相同，则称W为一条链，如果W顶点互不相同，则称W是一条路。链长是W中边的个数k。记路长uvwxyabdefgh|路：xcwhyeuav|链：wcxdyhwbvgyc第32页/共130页圈(回路)如果途径W的起点和终点相同且有正长度，则称它是一个闭途径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。圈：uavbwhyeuuvwxyabdefghc第33页/共130页定理一个图是二分图当且仅当图中不存在奇圈。第34页/共130页Euler圈Euler圈是指过所有边一次且恰好一次的闭途径。Euler链是指过所有边一次且恰好一次的链。Euler链:ydxcwheuavfygvbwuvwxyabdefghc第35页/共130页图例下例给出了一个图的径，链和路。径：uavfyfvgyhwbv链：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler链:ydxcwheuavfygvbwuvwxyabdefghc第36页/共130页Euler型定定理理定理定理2设G是连通圈，则G是Euler型的充要条件是G没有奇次数的顶点。推论1设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。第37页/共130页连通性图G称为连通的，如果在G的任意两个顶点u和v中存在一条(u,v)路。|不连通图至少有两个连通分支。两点顶点u和v等价当且仅当u和v中存在一条(u,v)路。表示G的连通分支数。第38页/共130页10.2 树树（tree）是一个不包含圈的简单连通图。具有k个连通分支的不包含圈的图称为k-树，或森林。第39页/共130页下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。第40页/共130页性质1设G是一棵树，则：G中任意两点均有唯一的路连接。2 G的边数等于顶点数减1，即3 若G不是平凡图，则G至少有两个次数为1的顶点。第41页/共130页定理1设G是一个简单图，则下列六个命题是等价的。G是一棵树。无圈且m=n-1。G连通且m=n-1。G连通并且每条边都是割边。G中任意两点都有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。第42页/共130页支撑树图G的支撑树是G的支撑子图，并且是一棵树。每个连通图都有支撑树支撑树也称为连通图的极小连通支撑子图。很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。第43页/共130页定理v定理4设T1 和T2 是G的两个支撑树，令 则T1 经过k次迭代后可得到T2。v定理2设G是一个连通图，T是G的一棵支撑树，e是G的一条不属于T的边，则T+e含有G的唯一圈。v定理3设T是连通图G的一棵支撑树，e是T的任意一条边，则：T（1）不包含G的割集（2）包含G的唯一的割集。第44页/共130页最小树定理5设T是G的一个支撑树，则T是G的最小树的充分必要条件为对任意边设G是一个赋权图，T为G的一个支撑树。定义T的权为：G中权最小的支撑树称为G的最小树。第45页/共130页定理6设T是G的支撑树，则T是G的最小树的充分必要条件为对任意边 ，其中 为G的唯一割集。第46页/共130页最小树算法-1-贪心算法Kruskal在1965年提出一种求最小树的所谓贪心算法。算法步骤如下vStep0 把边按权的大小从小到大排列得：置Step1 若 ，则停，此时GS即为所求的最小树；否则，转向Step2。Step2 如果 GS+e j不构成回路，则令转向Step1；否则，令j=j+1转向Step2。第47页/共130页算例图7-18展示了利用Kruskal算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-18第48页/共130页v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1第49页/共130页评注Kruskal算法的总计算量为 ，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的 个独立割集中，取每个割集的一条极小边来构成最小树。第50页/共130页最小树算法-2-Dijkstra算法Step0 置Step1 取置Step2 若 ，则停止；否则，置 ，返回Step1第51页/共130页算例2图7-19展示了利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19第52页/共130页利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-19-1第53页/共130页破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1 若G不含圈，则停止；否则在G中找一个圈C，取圈C的一条边e ，满足最小树算法-3-破圈法Step2：置 G=G-e，返回Step1。利用破圈法求图7-19的最小树的过程如图7-20所示。第54页/共130页算例3图7-20展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图图7-20第55页/共130页v1v2v4v5v312244342v1v2v4v5v312244342图图7-20-1第56页/共130页评注上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。给 定 一 个 赋 权 图 G，可 以 相 应 地 定 义 一 个 邻 接 矩 阵A=(wij)，其中wij是连接顶点vi和vj的权;若vi vj不是G的边，则令 wij 等于无穷大。第57页/共130页Step0：画掉第一列的所有元素（例如打上 ），并在第一行的每个元素下面画一横线。Step1：在画横线的元素中找一个最小的w ij，用圆圈起来，把第j列其他元素画掉，并把第j行没有画掉的元素画上横线。Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。最小树算法-4-表上作业法第58页/共130页算例用表上作业法求图7-19的最小树的过程为：最小对的权=1+2+3+2=8。v1v2v4v5v312244342第59页/共130页第60页/共130页最小连接问题作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为cij，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。第61页/共130页10.3 最短路问题最短路问题vDijkstra算法v求任意两点的最短路算法-Floyd算法v求带负权网络图的最短路的算法v用线性规划求最短路第62页/共130页赋权图v给定赋权图的一个子图H，定义H的权为H的所有边权的总和。n对图G的每条边e，赋予一实数(e)，称为边e的权，可得一赋权图。SDBTCEA712244731555第63页/共130页赋权图中一条路的权称为路长。n在一个赋权图G上，给定两个顶点u和 v，所谓u和 v最短 路是指所有连接顶点u和 v 的路中路长最短的路；nu和v最短路的路长也称为u和 v的距离。SDBTCEA712244731555n如何求从u到v的最短路的长？第64页/共130页Dijkstra算法的基本思想：(1)u0u1P设S是V的真子集，如果 是从u0 到的最短路，则，并且P的 段是最短的 路，所以第65页/共130页算法标号令dij表示连接顶点vi与顶点vj边上的权，即(1)公式（1）是Dijkstra算法的基础。第66页/共130页定义结点vj 的标号为始点的标号为始点的标号为0,-,表明这个点前面没有点。表明这个点前面没有点。结点结点vj 的标号分为两种：的标号分为两种：临时性标号和永久性标号临时性标号和永久性标号。如果。如果找到一条更短的路，临时性标号即被修改，如果找不到一找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。条更短的路，临时性标号即被改为永久性标号。第67页/共130页vStep0 令始点的标号为0,-.令i=1 Step i(a)对于由结点i可达的还没有永久性标号的结点j，计算其临时性标号li+dij,i（dij0）.如果 j 已经通过另一个结点k标号为 lj,k 且 li+dijlj,则用li+dij,i取代 lj,k。(b)如果所有的结点都是永久性标号，停止。否则选择最小如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号的临时性标号 lr,s。令令 i=r，返回返回Step i.第68页/共130页计算实例求连接求连接S、T的最短路的最短路SDBTCEA712244731555第69页/共130页SDBTCEA7122447315550第70页/共130页SDBTCEA71224473155505，s4，s2，s2，s第71页/共130页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s第72页/共130页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C第73页/共130页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，B第74页/共130页SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E第75页/共130页lST=13;S-T最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第76页/共130页实例评述Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第77页/共130页注注:Dijkstra算法只适用于所有算法只适用于所有wij0的情形，当赋权有向图中的情形，当赋权有向图中存在负权时，算法失效。如存在负权时，算法失效。如v1v2v3 12-3用用Dijkstra算法可以得出从算法可以得出从v1到到v2的最短路的权是的最短路的权是1，但实际上，但实际上从从v1到到v2的最短路是（的最短路是（v1，v3，v2），权是），权是-1。第78页/共130页下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再沿（，再沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这条路必定是从的这条路必定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必）必满足如下方程：满足如下方程：第79页/共130页第80页/共130页6-1-3-283-52-111-1217-3-5例：求例：求v1到各点的最短路。到各点的最短路。第81页/共130页wijv1v2v3v4v5v6v7v8t=1t=2t=3t=4v10-1-230000v2602-1-5-5-5v3-30-51-2-2-2-2v4023-7-7-7v5-101-3-3v610-17-1-1-1v7-1-305-5-5v8-5066第82页/共130页例一个连接11个城镇的交通图以及城市u与v之间的一条最短路。（粗线表示）uv第83页/共130页uv第84页/共130页求任意两点的最短路算法求任意两点的最短路算法-Floyd算法算法这种算法用一个这种算法用一个n阶方阵来表示一个阶方阵来表示一个n-结点网络结点网络.矩阵中的矩阵中的(i,j)-元元 dij 表示从表示从 i 到到 j边上的权边上的权,即即第85页/共130页ijkFloyds algorithm 的基本思想：给定结点的基本思想：给定结点 i,j 和和 k，若有如，若有如下三角形，且下三角形，且 ，则从，则从i经过经过 k到到j 比直接到比直接到j所经所经过路线短。过路线短。此时用此时用ikj 代替代替ij最好最好.-三角形运算三角形运算第86页/共130页第87页/共130页1245335461510 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234第88页/共130页 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234第89页/共130页 1 2 3 4 5 1 2 3 4 5310313510136155644 1 2 3 4 5 1 2 3 4 523451145114512351234 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 5232511451145223512341 2 3 4 5第90页/共130页 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 523251145114522351234 1 2 3 4 5310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 51 2 3 4 5第91页/共130页 1 2 3 4 5310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 5 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 5第92页/共130页 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 512453354615101245第93页/共130页用线性规划求最短路124531001550106030求从求从1到到2的最短路的最短路20第94页/共130页10.4 网络最大流问题第95页/共130页vsv1v3v4v2vt322223111网络流图网络流图设D=(V,A,W)是一个有向网络。vs是网络的源点，vt是网络的汇点。弧上的数字是允许通过的最大流量。第96页/共130页可行流设f是定义在弧集A上的一个函数，如果对所有弧 a 成立并且对所有中间顶点中间顶点 v 成立其中，f+(v)是流出v 的流量，f -(v)是流入v的流量。则称 f 是网络D上的一个可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1-容量限制-守恒条件第97页/共130页流值对于源点vs和汇点vt，流出源点vs的流量等于流入汇点vt的流量，称之为流 f 的值，记为val f。即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f=3第98页/共130页最大流网络最大流是指给定网络上的流值最大的一个可行流。网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。Ford 与 Fulkerson 在1957年提出一个求解网络最大流问题的算法，称为Ford Fulkerson 算法。第99页/共130页割集设S是网络的顶点子集，且割集的容量定义为最小割是指容量最小的割。定义D的一个割集，简称割为vsv1v3v4v2vt322223111第100页/共130页定理1对于网络的任意流 f 和割 成立证明 由定义可知第101页/共130页推论1 对于网络的任意流 f 和割 ，成立vsv1v3v4v2vt322223111第102页/共130页注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。则f 是最大流，K是最小割。如果成立推论2 设 f 是网络的一个可行流，是网络的一个割，第103页/共130页链、正向弧、反向弧 设P是网络D的一条链，则P中的弧可分为两类：正向弧弧的方向与P的走向一致；记为P+。反向弧弧的方向与P的走向相反;记为P-。网络D的连接源点vs和汇点vt的路。vsv1v3v4v2vt322223111第104页/共130页增广链设P是网络D的一条连接源点vs和汇点vt的链，f 是网络D上的一个可行流.n如果P的每一正向弧都是不饱和弧，而P的每一反向弧的流量都为正；n则称P是网络D的关于可行流f 的一条可增广链。简称增广链。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,21,01,11,0第105页/共130页定理2设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在f 的增广链。证明 （必要性）设f 是一个最大流，假如D中存在f 的增广链P,则可以得到一个流值更大的流f 1,使得v构造过程如下：其中其中第106页/共130页证明n充分性设网络D不存在f 的增广链。定义S如下：从而 是D的割集，进而可得 中的弧都是饱和弧，而 中的弧都是0流弧，否则将产生网络D 的一条增广链。因此，f 的流值等于割集 的割量，所以，f是一个最大流。第107页/共130页定理3在任何网络流图中，最大流的值等于最小割的容量。在任何网络流图中，最大流的值等于最小割的容量。（最大流最小割定理）（最大流最小割定理）第108页/共130页Ford Fulkerson 算法Ford Fulkerson 算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。定理的证明过程蕴涵着最大流算法定理的证明过程蕴涵着最大流算法第109页/共130页算例求下面网络的最大流vsv1v3v4v2vt852879665图图4.23第110页/共130页初始0流先给网络赋一个初始0流f 0 图图4.2-1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第111页/共130页(+vs,8)(+vs,2)(-,)寻找增广链1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第112页/共130页vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)寻找增广链2第113页/共130页vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)(+v2,5)寻找增广链3第114页/共130页寻找增广链4v找到流f 0 的增广链P0=vs v1 v2 vt.vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs,8)(+vs,2)(-,)(+v1,5)(+v3,2)(+v2,5)|增量=5.第115页/共130页调整流值2v调整流值得流值为5的新可行流f 1，vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0第116页/共130页vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)第117页/共130页vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)(+v3,2)(+v3,2)第118页/共130页vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)(+v3,2)(+v3,2)(+v2,2)第119页/共130页|增量=2.vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs,3)(+vs,2)(-,)(+v3,2)(+v3,2)(+v2,2)v找到流f 1 的增广链P0=vs v3 v2 vt，第120页/共130页调整流值3v调整流值得流值为7的新可行流f 2，vsv1v3v4v2vt8,55,52,28,07,09,76,06,05,23,0第121页/共130页vsv1v3v4v2vt8,55,52,28,07,09,76,06,05,23,0(+vs,3)(+v1,3)(-,)(+v3,3)(+v3,3)(+v2,2)|增量=2.第122页/共130页vsv1v3v4v2vt8,75,52,28,07,09,96,26,05,43,0第123页/共130页vsv1v3v4v2vt8,75,52,28,07,09,96,26,05,43,0(+vs,1)(+v1,1)(-,)(+v3,1)(+v3,1)(+v4,1)|增量=1.第124页/共130页vsv1v3v4v2vt8,85,52,28,17,19,96,36,05,43,0第125页/共130页vsv1v3v4v2vt8,85,52,28,17,19,96,36,05,43,0(-,)寻找增广链v利用标号法得不出流f 3 的增广链，因此，f 3 是给定网络的最大流，流值为10。v令S=vs,则 是最小割。第126页/共130页Ford Fulkerson 算法vStep0 先给网络赋一个初始0流f 0;给vs标(-,+)v Step1 寻找流f 的增广链(1.1)如果所有标号点已经检查且汇点未标号，转Step3；(1.2)找一个已标号但未检查的点vi 做如下检查：对每个弧e=(vi,vk),如果vk 未标号且)()(),(min)(efecilkl-=则给vk标号(+vi,l(k),其中第127页/共130页Ford Fulkerson 算法 对每个 弧e=(vk,vi),如果vk 未标号且 则给v k标号(-vi,l(k),其中)(),(min)(efilkl=Step2 增广网络流 从源点vs开始依据标号构造增广链P，并调整流值，标号的正负表示增加或减少相应弧的流值；擦去所 有标号，转Step1.(1.3)若汇点vt已标号，转Step2;否则转(1.1).Step3 令S表示所有已标号点，则得最小割，相应流为 最大流，结束。第128页/共130页1235468528796653Linear Programming of Maximal Flow Mode第129页/共130页感谢您的观看！第130页/共130页