运筹学 图与网络优化

1、运筹学 图与网络优化第1页，共131页，2022年，5月20日，18点42分，星期三图论概述图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。第2页，共131页，2022年，5月20日，18点42分，星期三网络规划概述网络规划(Network Programming )是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。第3页，共131页，2022年，5月20日，18点42分，星期

2、三七桥问题七桥问题图形第4页，共131页，2022年，5月20日，18点42分，星期三原 理 及 方 法 七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。第5页，共131页，2022年，5月20日，18点42分，星期三10.1 图的基本概念一个图(Graph) 定义为三元有序组V(G)是图的顶点集合E(G)是图的边集合记 是关联函数第6页，共131页，2022年，5月20日，18点42分，星期三图的端点设G是一个图(Graph)G=(V(G),E(G)，则称e连接u和v，称u和v是e的端点

3、。若称端点u，v与边e是关联的，称两个顶点u，v是邻接的。第7页，共131页，2022年，5月20日，18点42分，星期三设G是一个图， 图10G的几何实现第8页，共131页，2022年，5月20日，18点42分，星期三图的几何实现 一个图可用一个几何图形表示,称为图的几何实现，其中每个顶点用点表示，每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的许多性质。第9页，共131页，2022年，5月20日，18点42分，星期三说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自

4、身. 并称图形的点为顶点，图形的线为边。图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。第10页，共131页，2022年，5月20日，18点42分，星期三几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图 中，它共有4个顶点，6条边；而e 3 与e 4 的交点不是这个图的顶点。第11页，共131页，2022年，5月20日，18点42分，星期三平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。下图就是一个平面图。第12页，共131页，2022年，5月20日，18点42分，星期三基本概念端点重合为一点的边称为环。连接同一对

5、顶点的多条边称为多重边。在右图中，e5 是一个环，e1 与e2 是多重边， v1和e1,e2,e3是关联的，v1与v2,v3是邻接的。第13页，共131页，2022年，5月20日，18点42分，星期三邻接矩阵设G是一个图， G=(V(G),E(G)，定义图G的邻接矩阵A(G) =(aij)为mm矩阵, aij是顶点vi与边vj相邻接的边数。其中第14页，共131页，2022年，5月20日，18点42分，星期三关联矩阵设G是一个图， G=(V(G),E(G)定义图G的关联矩阵M=(mij)为mn矩阵；其中mij是顶点vi与边ej相关联的次数，取值可能为0、1、2。第15页，共131页，2022年

6、，5月20日，18点42分，星期三注图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。第16页，共131页，2022年，5月20日，18点42分，星期三顶点的度设G是一个图， G=(V(G),E(G)，定义图G的顶点v的度为与顶点v相关联的边数，记作d(v) 例称度为奇数的顶点为奇点；称度为偶数的顶点为偶点。第17页，共131页，2022年，5月20日，18点42分，星期三例22222224+3+3+4=14=27第18页，共131页，2022年，5月20日，18点42分，星期三关联矩阵性质图G的关联矩阵M=(mij)为mn矩阵；

7、则每行元素之和等于相应顶点的度；每列元素之和等于2。因此，图G的关联矩阵M所有元素之和既等于所有顶点的度之和，又等于边数的2倍。定理设G是一个图，则第19页，共131页，2022年，5月20日，18点42分，星期三推论图中奇点的数目为偶数。证明记第20页，共131页，2022年，5月20日，18点42分，星期三简单图一个图称为简单图，如果它既没有环也没有多重边。下图是简单图。本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为平凡图；边集是空集的图称为空图。第21页，共131页，2022年，5月20日，18点42分，星期三同构称G

8、和H是同构的，记为 ，使得给定两个图如果存在两个一一对应第22页，共131页，2022年，5月20日，18点42分，星期三同构图例图G与图H是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4第23页，共131页，2022年，5月20日，18点42分，星期三完全图Kn完全图是每一对不同顶点都恰有一边的简单图；具有n个顶点的完全图记为Kn.K5第24页，共131页，2022年，5月20日，18点42分，星期三二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，使得每条边的一个端点在X，另一个端点在Y; (X,Y)也称为图的二分划。x1x2x3y1

9、y2y3第25页，共131页，2022年，5月20日，18点42分，星期三完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的每个顶点与Y的每个顶点都相连；记为Km,n，其中K3,3第26页，共131页，2022年，5月20日，18点42分，星期三特殊图例K5K 3,3都是极小的非平面图第27页，共131页，2022年，5月20日，18点42分，星期三子图称图H是图G的子图，图G及其基本图称H是G的支撑子图，如果称H是G的真子图，若如果表示关联函数记为在H的限制。第28页，共131页，2022年，5月20日，18点42分，星期三顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以

10、二端点均在W中的边的全体为边集的子图称为由W导出的G的子图，简称导出子图，记为GW。导出子图GV- w记为G-W，即 它是从G中删除W中顶点以及与这些顶点相关联的边所得到的子图。如果W仅含一个顶点v，则把 简记为。第29页，共131页，2022年，5月20日，18点42分，星期三边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点全体为顶点集所构成的子图称为由F导出的G的子图，简称G的边导出子图。记为GF。记G-F表示以E(G)F为边集的G的支撑子图，它是从G中删除F中的边所得到的子图。如F= e ，则记。第30页，共131页，2022年，5月20日，18点42分，星期三子图图例v1v

11、2v3v4v5e1e3e2Gv1v2v3v4v5G的支撑子图G- e1 , e 2 , e 3第31页，共131页，2022年，5月20日，18点42分，星期三子图图例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2 ,v 5 v1v2v3v4e1e3e2G e1 , e 2 , e 3v1v2v3v4v5e1e3e2G第32页，共131页，2022年，5月20日，18点42分，星期三途径顶点vk叫W的终点，顶点v0 称为W的起点，顶点vi 叫W的内部顶点，整数k称为W的长度。在简单图中，径可由顶点序列表示。图G的一个有限的点边交错序列称为从v0到vk的途径。其中vi与vi+

12、1是边ei的顶点;第33页，共131页，2022年，5月20日，18点42分，星期三路、链如果径W的边不相同，则称W为一条链，如果W顶点互不相同，则称W是一条路。链长是W中边的个数k。记路长uvwxyabdefgh路：xcwhyeuav链：wcxdyhwbvgyc第34页，共131页，2022年，5月20日，18点42分，星期三圈(回路)如果途径W的起点和终点相同且有正长度，则称它是一个闭途径；如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。圈：uavbwhyeuuvwxyabdefghc第35页，共131页，2022年，5月20日，1

13、8点42分，星期三定理一个图是二分图当且仅当图中不存在奇圈。第36页，共131页，2022年，5月20日，18点42分，星期三Euler圈Euler圈是指过所有边一次且恰好一次的闭途径。Euler链是指过所有边一次且恰好一次的链。Euler链:ydxcwheuavfygvbwuvwxyabdefghc第37页，共131页，2022年，5月20日，18点42分，星期三图例下例给出了一个图的径，链和路。径：uavfyfvgyhwbv链：wcxdyhwbvgy路：xcwhyeuav圈：uavbwhyeuEuler链:ydxcwheuavfygvbwuvwxyabdefghc第38页，共131页，20

14、22年，5月20日，18点42分，星期三Euler型定理定理2设G是连通圈，则G是Euler型的充要条件是G没有奇次数的顶点。推论1设G是一个连通图，则G有Euler链当且仅当G最多有两个奇数次数的顶点。第39页，共131页，2022年，5月20日，18点42分，星期三连通性图G称为连通的，如果在G的任意两个顶点u和v中存在一条(u,v)路。不连通图至少有两个连通分支。两点顶点u和v等价当且仅当u和v中存在一条(u,v)路。表示G的连通分支数。第40页，共131页，2022年，5月20日，18点42分，星期三10.2 树树（tree）是一个不包含圈的简单连通图。具有k个连通分支的不包含圈的图称

15、为k-树，或森林。第41页，共131页，2022年，5月20日，18点42分，星期三下图列出了具有六个顶点的不同构的树。从中可以看出，图中的每棵树都只有5条边，并且至少有2个顶点的次数是1。第42页，共131页，2022年，5月20日，18点42分，星期三性质1设G是一棵树，则： G中任意两点均有唯一的路连接。2 G的边数等于顶点数减1，即3 若G不是平凡图，则G至少有两个次数为1的顶点。第43页，共131页，2022年，5月20日，18点42分，星期三定理1设G是一个简单图， ，则下列六个命题是等价的。G是一棵树。无圈且m=n-1。G连通且m=n-1。G连通并且每条边都是割边。G中任意两点都

16、有唯一的路相连。G无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。第44页，共131页，2022年，5月20日，18点42分，星期三支撑树图G的支撑树是G的支撑子图，并且是一棵树。每个连通图都有支撑树支撑树也称为连通图的极小连通支撑子图。很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。第45页，共131页，2022年，5月20日，18点42分，星期三定理定理4设T1 和T2 是G的两个支撑树，令 则T1 经过k次迭代后可得到T2。定理2设G是一个连通图，T是G的一棵支撑树，e是G的一条不属于T的边，则T+e含有G的唯一圈。定理3设T是连通图G的一棵支撑树，e是T的

17、任意一条边，则：T（1） 不包含G的割集（2）包含G的唯一的割集。第46页，共131页，2022年，5月20日，18点42分，星期三最小树定理5设T是G的一个支撑树，则T是G的最小树的充分必要条件为对任意边设G是一个赋权图，T为G的一个支撑树。定义T的权为：G中权最小的支撑树称为G的最小树。第47页，共131页，2022年，5月20日，18点42分，星期三定理6设T是G的支撑树，则T是G的最小树的充分必要条件为对任意边 ，其中 为G的唯一割集。第48页，共131页，2022年，5月20日，18点42分，星期三最小树算法-1-贪心算法Kruskal在1965年提出一种求最小树的所谓贪心算法。算法

18、步骤如下Step0 把边按权的大小从小到大排列得：置Step1 若 ，则停，此时GS即为所求的最小树； 否则，转向Step2。Step2 如果 GS+e j不构成回路，则令转向Step1；否则，令j=j+1转向Step2。第49页，共131页，2022年，5月20日，18点42分，星期三算例图7-18展示了利用Kruskal算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-18第50页，共131页，2022年，5月20日，18点42分，星期三v1v2v4v5v312244342v1v2v4v5v312244342图7-18-1第51页，共13

19、1页，2022年，5月20日，18点42分，星期三评注Kruskal算法的总计算量为 ，有效性不太好。求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的 个独立割集中，取每个割集的一条极小边来构成最小树。第52页，共131页，2022年，5月20日，18点42分，星期三最小树算法-2 -Dijkstra算法Step0 置Step1 取置Step2 若 ，则停止；否则，置 ，返回Step1第53页，共131页，2022年，5月20日，18点42分，星期三算例2图7-19展示了利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v

20、5v312244342图7-19第54页，共131页，2022年，5月20日，18点42分，星期三利用Dijkstra算法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-19-1第55页，共131页，2022年，5月20日，18点42分，星期三破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1 若G不含圈，则停止；否则在G中找一个圈C，取圈C的一条边e ，满足最小树算法-3 -破圈法Step2：置 G = G - e ，返回Step1。利用破圈法求图7-19的最小树的过程如

21、图7-20所示。第56页，共131页，2022年，5月20日，18点42分，星期三算例3图7-20展示了利用破圈法求最小树的迭代过程。v1v2v4v5v312244342v1v2v4v5v312244342图7-20第57页，共131页，2022年，5月20日，18点42分，星期三v1v2v4v5v312244342v1v2v4v5v312244342图7-20-1第58页，共131页，2022年，5月20日，18点42分，星期三评注上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。给定一个赋权图G，可以相应地定义一个邻接矩阵A=(wij)，其中wij是连接顶点

22、vi和vj的权;若vi vj不是G的边，则令 wij 等于无穷大。第59页，共131页，2022年，5月20日，18点42分，星期三Step0：画掉第一列的所有元素（例如打上 ）， 并在第一行的每个元素下面画一横线。Step1：在画横线的元素中找一个最小的w ij ，用圆圈起来，把第j列其他元素画掉，并把第j行没有画掉的元素画上横线。Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。最小树算法-4 -表上作业法第60页，共131页，2022年，5月20日，18点42分，星期三算例用表上作业法求图7-

23、19的最小树的过程为：最小对的权=1+2+3+2=8。v1v2v4v5v312244342第61页，共131页，2022年，5月20日，18点42分，星期三第62页，共131页，2022年，5月20日，18点42分，星期三最小连接问题作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇i和j之间直通线路的造价为cij，试设计一个总造价最小的铁路运输图。把每个城镇看作是具有权cij的赋权图G的一个顶点。显然连接问题可以表述成：在赋权图G中，求出具有最小权的支撑树。第63页，共131页，2022年，5月20日，18点42分，星期三10.3 最短路问题D

24、ijkstra算法求任意两点的最短路算法-Floyd算法求带负权网络图的最短路的算法用线性规划求最短路第64页，共131页，2022年，5月20日，18点42分，星期三赋权图给定赋权图的一个子图H，定义H的权为H的所有边权的总和。对图G的每条边e，赋予一实数(e)，称为边e的权，可得一赋权图。SDBTCEA712244731555第65页，共131页，2022年，5月20日，18点42分，星期三赋权图中一条路的权称为路长。在一个赋权图G上，给定两个顶点u和 v，所谓u和 v最短 路是指所有连接顶点u和 v 的路中路长最短的路；u和v最短路的路长也称为u和 v的距离。SDBTCEA7122447

25、31555如何求从u到v的最短路的长？第66页，共131页，2022年，5月20日，18点42分，星期三Dijkstra算法的基本思想：(1)u0u1P设S是V的真子集，如果 是从u0 到的最短路，则 ，并且P的 段是最短的 路，所以第67页，共131页，2022年，5月20日，18点42分，星期三算法标号令dij表示连接顶点vi与顶点vj边上的权，即(1)公式（1）是Dijkstra算法的基础。第68页，共131页，2022年，5月20日，18点42分，星期三定义结点vj 的标号为始点的标号为0,-, 表明这个点前面没有点。结点vj 的标号分为两种：临时性标号和永久性标号。如果找到一条更短的

26、路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。第69页，共131页，2022年，5月20日，18点42分，星期三Step0 令始点的标号为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.第70页，共131页，2022年，5月20日，18点42

27、分，星期三计算实例求连接S、T的最短路SDBTCEA712244731555第71页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA7122447315550第72页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA71224473155505，s4，s2，s2，s第73页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s第74页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，

28、A4，s4，A8，C第75页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B 7，B第76页，共131页，2022年，5月20日，18点42分，星期三SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E第77页，共131页，2022年，5月20日，18点42分，星期三lST = 13;S-T最短路为SABEDTSDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，

29、B8，E14，E8，E13，D第78页，共131页，2022年，5月20日，18点42分，星期三实例评述Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。SDBTCEA71224473155505，s4，s2，s2，s9，A4，A4，s4，A8，C7，B7，B8，E14，E8，E13，D第79页，共131页，2022年，5月20日，18点42分，星期三注:Dijkstra算法只适用于所有wij0的情形，当赋权有向图中存在负权时，算法失效。如v1v2v3 12-3用Dijkstra算法可以得出从v1到v

30、2的最短路的权是1，但实际上从v1到v2的最短路是（v1， v3 ，v2），权是-1。第80页，共131页，2022年，5月20日，18点42分，星期三下面介绍具有负权赋权有向图D的最短路的算法。不妨假设从任一点vi到任一点vj都有一条弧（如果在D中，（ vi，vj ） A，则添加弧（ vi，vj ）令wij=+ ）。显然，从vs到任一点vj的最短路总是从vs出发到某个点vi，再沿（vi，vj）到vj的，由前面的结论可知，从vs到vi的这条路必定是从vs到vi的最短路，所以d（vs，vj）必满足如下方程：第81页，共131页，2022年，5月20日，18点42分，星期三第82页，共131页，2

31、022年，5月20日，18点42分，星期三6-1-3-283-52-111-1217-3-5例：求v1到各点的最短路。第83页，共131页，2022年，5月20日，18点42分，星期三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第84页，共131页，2022年，5月20日，18点42分，星期三例一个连接11个城镇的交通图以及城市u与v之间的一条最短路。（粗线表示）uv第85页，共131页，2

32、022年，5月20日，18点42分，星期三uv第86页，共131页，2022年，5月20日，18点42分，星期三求任意两点的最短路算法-Floyd算法这种算法用一个n阶方阵来表示一个n-结点网络.矩阵中的 (i, j)-元 dij 表示从 i 到 j边上的权, 即第87页，共131页，2022年，5月20日，18点42分，星期三ijkFloyds algorithm 的基本思想：给定结点 i, j 和 k ，若有如下三角形，且 ，则从i经过 k到j 比直接到j所经过路线短。此时用ikj 代替ij最好.-三角形运算第88页，共131页，2022年，5月20日，18点42分，星期三第89页，共13

33、1页，2022年，5月20日，18点42分，星期三1245335461510 1 2 3 4 5 1 2 3 4 531035106155644 1 2 3 4 5 1 2 3 4 523451345124512351234第90页，共131页，2022年，5月20日，18点42分，星期三 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第91

34、页，共131页，2022年，5月20日，18点42分，星期三 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第92页，共131页，2022年，5月20日，18点42分，星期三 1 2 3 4 531083135101361585644 1 2 3 4 5 1 2 3 4 523251145114522351234 1 2 3 4 5

35、310825313528101361585644 1 2 3 4 5 1 2 3 4 5232311431145223512341 2 3 4 51 2 3 4 5第93页，共131页，2022年，5月20日，18点42分，星期三 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第94页，共131页，2022

36、年，5月20日，18点42分，星期三 1 2 3 4 53108123115910116108564129104 1 2 3 4 5 1 2 3 4 5232414441444223544441 2 3 4 512453354615101245第95页，共131页，2022年，5月20日，18点42分，星期三用线性规划求最短路124531001550106030求从1到2的最短路20第96页，共131页，2022年，5月20日，18点42分，星期三10.4 网络最大流问题第97页，共131页，2022年，5月20日，18点42分，星期三vsv1v3v4v2vt322223111网络流图设D=

37、(V,A,W) 是一个有向网络。vs是网络的源点，vt是网络的汇点。弧上的数字是允许通过的最大流量。第98页，共131页，2022年，5月20日，18点42分，星期三可行流设f是定义在弧集A上的一个函数，如果对所有弧 a 成立并且对所有中间顶点 v 成立其中，f +(v)是流出v 的流量，f -(v)是流入v的流量。则称 f 是网络D上的一个可行流。2,1vsv1v3v4v2vt3,12,12,22,13,21,01,01,1-容量限制-守恒条件第99页，共131页，2022年，5月20日，18点42分，星期三流值对于源点vs和汇点vt ，流出源点vs的流量等于流入汇点vt的流量，称之为流 f

38、 的值，记为val f 。即vsv1v3v4v2vt3,12,12,22,12,13,21,01,01,1val f = 3第100页，共131页，2022年，5月20日，18点42分，星期三最大流网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。Ford 与 Fulkerson 在1957年提出一个求解网络最大流问题的算法，称为Ford Fulkerson 算法。第101页，共131页，2022年，5月20日，18点42分，星期三割集设S是网络的顶点子集，且割集的容量定义为最小割是指容量最小的割。定义D的一个割集，简称割为vsv1v3v

39、4v2vt322223111第102页，共131页，2022年，5月20日，18点42分，星期三定理1对于网络的任意流 f 和割 成立证明 由定义可知第103页，共131页，2022年，5月20日，18点42分，星期三推论1 对于网络的任意流 f 和割 ，成立vsv1v3v4v2vt322223111第104页，共131页，2022年，5月20日，18点42分，星期三注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。则f 是最大流，K是最小割。如果成立推论2 设 f 是网络的一个可行流， 是网络的一个割，第105页，共131页，2022年，5月2

40、0日，18点42分，星期三链、正向弧、反向弧 设P是网络D的一条链，则P中的弧可分为两类：正向弧弧的方向与P的走向一致；记为P+。反向弧弧的方向与P的走向相反;记为P-。网络D的连接源点vs和汇点vt的路。vsv1v3v4v2vt322223111第106页，共131页，2022年，5月20日，18点42分，星期三增广链设P是网络D的一条连接源点vs和汇点vt的链， f 是网络D上的一个可行流.如果P的每一正向弧都是不饱和弧，而P的每一反向弧的流量都为正；则称P是网络D的关于可行流f 的一条可增广链。简称增广链。可增广链上流量可以增加。vsv1v3v4v2vt3，12,12,22,22,13,

41、21,01,11,0第107页，共131页，2022年，5月20日，18点42分，星期三定理2设f 是网络D上的一个可行流，则 f 是一个最大流当且仅当网络D不存在f 的增广链。证明 （必要性） 设f 是一个最大流，假如D中存在f 的增广链P,则可以得到一个流值更大的流f 1,使得构造过程如下：其中第108页，共131页，2022年，5月20日，18点42分，星期三证明充分性设网络D不存在f 的增广链。定义S如下：从而 是D的割集，进而可得 中的弧都是饱和弧，而 中的弧都是0流弧， 否则将产生网络D 的一条增广链。因此，f 的流值等于割集 的割量，所以， f是一个最大流。第109页，共131页

42、，2022年，5月20日，18点42分，星期三定理3在任何网络流图中，最大流的值等于最小割的容量。（最大流最小割定理）第110页，共131页，2022年，5月20日，18点42分，星期三Ford Fulkerson 算法Ford Fulkerson 算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。定理的证明过程蕴涵着最大流算法第111页，共131页，2022年，5月20日，18点42分，星期三算例求下面网络的最大流vsv1v3v4v2vt852879665图4.23第112页，共131页，2022年，5月2

43、0日，18点42分，星期三初始0流先给网络赋一个初始0流f 0 图4.2-1vsv1v3v4v2vt8,05 ,02, 08 ,07 ,09 ,06 ,06 ,05, 03 ,0第113页，共131页，2022年，5月20日，18点42分，星期三(+vs, 8)(+vs, 2)(-, )寻找增广链1vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0第114页，共131页，2022年，5月20日，18点42分，星期三vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs, 8)(+vs, 2)(-, )(+v1, 5)(+v

44、3, 2)寻找增广链2第115页，共131页，2022年，5月20日，18点42分，星期三vsv1v3v4v2vt8,05,02,08,07,09,06,06,05,03,0(+vs, 8)(+vs, 2)(-, )(+v1, 5)(+v3, 2)(+v2, 5)寻找增广链3第116页，共131页，2022年，5月20日，18点42分，星期三寻找增广链4找到流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.第1

45、17页，共131页，2022年，5月20日，18点42分，星期三调整流值2调整流值得流值为5的新可行流f 1 ，vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0第118页，共131页，2022年，5月20日，18点42分，星期三vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs, 3)(+vs, 2)(-, )第119页，共131页，2022年，5月20日，18点42分，星期三vsv1v3v4v2vt8,55,52,08,07,09,56,06,05,03,0(+vs, 3)(+vs, 2)(-, )(+v3, 2)(+v3, 2)第120页，共131页，2022年，5月20日