数学建模图论详解—图论与网络规划课件

第七章 图论与网络规划第七章 图论与网络规划1 1图论概述图论概述n图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。图论概述图论(Graph Theory)是运筹学中的一个重要2网络规划概述网络规划概述n网络规划(Network Programming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。网络规划概述网络规划(Network Programming3七桥问题七桥问题七桥问题图形ACDB图论模型七桥问题七桥问题图形ACDB图论模型4原原 理理 及及 方方 法法 七桥问题是图论中的著名问题。1736年，Euler巧妙地将此问题化为图的不重复一笔画问题，并证明了该问题不存在肯定回答。原因在于该图形有顶点连接奇数条边。原 理 及 方 法 七桥问题是图论中的著名问题。1736年，57、1 图的基本概念图的基本概念一个图一个图(Graph)定义为三元有序组定义为三元有序组G=(V(G),E(G)，V(G)是图的顶点集合，是图的顶点集合，E(G)是图的边集合，是图的边集合，记记7、1 图的基本概念一个图(Graph)定义为三元6图的端点图的端点设设G是一个图是一个图(Graph)G=(V(G),E(G)，则称则称e连接连接u和和v，称，称u和和v是是e的端点。的端点。若若称端点称端点u，v与边与边e是是关联的关联的，称两个顶点称两个顶点u，v是是邻接邻接的。的。图的端点设G是一个图(Graph)则称e连接u和v，称u和v7设设G是一个图，是一个图，图G的几何实现的几何实现设G是一个图，图G的几何实现8图的几何实现图的几何实现 一个图可用一个几何图形表示一个图可用一个几何图形表示,称为称为图的几何实现，其中图的几何实现，其中每个顶点用点表示，每个顶点用点表示，每条边用连接端点的线表示。每条边用连接端点的线表示。图的几何实现有助与我们直观的了解图的几何实现有助与我们直观的了解图的许多性质。图的许多性质。图的几何实现 一个图可用一个几何图形表示,称为图的几何实现，9说明说明一个图的几何实现并不是唯一的；表示顶点的点和表示一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出边的线的相对位置并不重要，重要的是图形描绘出边与顶点之间保持的相互关系边与顶点之间保持的相互关系。我们常常把一个图的图形当作这个抽象图自身我们常常把一个图的图形当作这个抽象图自身.并称图形的点为顶点并称图形的点为顶点,图形的线为边，图形的线为边，图论中大多数概念是根据图的表示形式提出的，例如：图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。顶点、边、多重边、环、路、圈、树等。说明一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的10几何实现图例几何实现图例在一个图的几何实现中，两条边的交点可能不是图在一个图的几何实现中，两条边的交点可能不是图的顶点。例如图的顶点。例如图7-4 中，它共有中，它共有4个顶点，个顶点，6条边；条边；而而e 3 与与e 4 的交点不是这个图的顶点。的交点不是这个图的顶点。几何实现图例在一个图的几何实现中，两条边的交点可能不是图的顶11平面图平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在一个图称为平面图，如它有一个平面图形，使得边与边仅在顶点相交。图顶点相交。图7-5就是一个平面图，因为它可以有下面的图就是一个平面图，因为它可以有下面的图形。形。图平面图一个图称为平面图，如它有一个平面图形，使得边与边仅在图12基本概念基本概念端点重合为一点的边称为端点重合为一点的边称为环环。连接同一对顶点的多条边称为连接同一对顶点的多条边称为多重边多重边。在图在图7-3中，中，e5 是一个环，是一个环，e1 与与e2 是多重边，是多重边，v1和和e1,e2,e3是关联的，是关联的，v1与与v2,v3是邻接的。是邻接的。图基本概念端点重合为一点的边称为环。图13邻接矩阵邻接矩阵设设G是一个图，是一个图，G=(V(G),E(G)定义图定义图G的邻接矩阵的邻接矩阵A(G)=(aij)为为mm矩阵矩阵,aij是顶点是顶点vi与边与边vj相邻接的边数。相邻接的边数。其中其中邻接矩阵设G是一个图，G=(V(G),E(G)aij是顶14关联矩阵关联矩阵设设G是一个图，是一个图，G=(V(G),E(G)定义图定义图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；矩阵；其中其中mij是顶点是顶点vi与边与边ej相关联的次数，相关联的次数，取值可能为取值可能为0、1、2。关联矩阵设G是一个图，G=(V(G),E(G)定义图G的15注注n图的邻接矩阵比它的关联矩阵小的多，因而图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。图常常以其邻接矩阵的形式存贮与计算机中。关联矩阵和邻接矩阵统称图的矩阵表示。关联矩阵和邻接矩阵统称图的矩阵表示。注图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的16顶点的度顶点的度设设G是一个图，是一个图，G=(V(G),E(G)定义图定义图G的顶点的顶点v的度为与顶点的度为与顶点v相关联的边相关联的边数，记作数，记作d(v)例例称度为奇数的顶点为奇点；称度为奇数的顶点为奇点；称度为偶数的顶点为偶点；称度为偶数的顶点为偶点；顶点的度设G是一个图，G=(V(G),E(G)例称度为17例例2222 2224+3+3+4=14=27例22222224+3+3+4=14=2718关联矩阵性质关联矩阵性质图图G的关联矩阵的关联矩阵M=(mij)为为mn矩阵；则矩阵；则每行元素之和等于相应顶点的度；每行元素之和等于相应顶点的度；每列元素之和等于每列元素之和等于2因此，因此，图图G的关联矩阵的关联矩阵M所有元素之和所有元素之和既等于所有顶点的度之和，既等于所有顶点的度之和，又等于边数的又等于边数的2倍。倍。定理设定理设G G是一个图，则是一个图，则关联矩阵性质图G的关联矩阵M=(mij)为mn矩阵；则因此19推论推论|图中奇点的数目为偶数。图中奇点的数目为偶数。证明证明记记推论图中奇点的数目为偶数。证明记20简单图简单图一个图称为一个图称为简单图简单图，如果，如果它既没有环也没有多重边它既没有环也没有多重边。下图下图5是简单图。是简单图。本书只限于讨论有限简单图，本书只限于讨论有限简单图，即顶点集与边集都是有限集的图。即顶点集与边集都是有限集的图。u1u2u3u4f1f2f6f3f5f4只有一个顶点的图称为只有一个顶点的图称为平凡图平凡图；边集是空集的图称为边集是空集的图称为空图空图。简单图一个图称为简单图，如果u1u2u3u4f1f2f6f321同构同构给定两个图给定两个图 与与称称G和和H是同构的，记为是同构的，记为，如果存在两个一一对应如果存在两个一一对应使的使的同构给定两个图 22同构图例同构图例n图图G与图与图H是同构的。是同构的。v1v2v3v4u1u2u3u4GHe6e4e2e1e3e5f1f2f6f3f5f4同构图例图G与图H是同构的。v1v2v3v4u1u2u3u423完全图K nn完全图是每一对不同顶点都恰有一边的简单图；完全图是每一对不同顶点都恰有一边的简单图；n具有具有n个顶点的完全图记为个顶点的完全图记为K n.K5完全图K n完全图是每一对不同顶点都恰有一边的简单图；K524二分图二分图n二分图是一个简单图，其顶点集合可分划成两个子集二分图是一个简单图，其顶点集合可分划成两个子集X与与Y，使得每条边的一个端点在，使得每条边的一个端点在X，另一个端点在，另一个端点在Y;(X,Y)也也称为图的二分划。称为图的二分划。x1x2x3y1y2y3二分图二分图是一个简单图，其顶点集合可分划成两个子集X与Y，25完全二分图完全二分图n完全二分图是具有二分划完全二分图是具有二分划(X,Y)的二分图，并且的二分图，并且X的每个顶点与的每个顶点与Y的每个顶点都相连；记为的每个顶点都相连；记为K m,n，n其中其中K 3,3完全二分图完全二分图是具有二分划(X,Y)的二分图，并且X的26特殊图例特殊图例K5K 3,3都是极小的非平面图都是极小的非平面图特殊图例K5K 3,3都是极小的非平面图27子图子图称图称图H是图是图G的子图，的子图，图图G及其基本图及其基本图称称H是是G的的支撑子图支撑子图，如果如果称称H是是G的真子图的真子图，若若如果如果表示关联函数表示关联函数记为记为在在H的限制。的限制。子图称图H是图G的子图，图G及其基本图称H是G的支撑子图28顶点导出子图顶点导出子图设设W是图是图G的一个非空顶点子集的一个非空顶点子集,以以W为顶点集，以二端为顶点集，以二端点均在点均在W中的边的全体为边集的子图称为由中的边的全体为边集的子图称为由W导出的导出的G的的子图，简称导出子图，记为子图，简称导出子图，记为GW。导出子图导出子图GV-w记为记为G-W，即，即 它是从它是从G中删除中删除W中顶点以及与这些顶点相关联的边所得中顶点以及与这些顶点相关联的边所得到的子图。到的子图。如果如果W仅含一个顶点仅含一个顶点v，则把，则把 简记为。简记为。顶点导出子图设W是图G的一个非空顶点子集,以W为顶点集，以二29边导出子图边导出子图设设F是图是图G的非空边子集，以的非空边子集，以F为边集，以为边集，以F中中边的端点全体为顶点集所构成的子图称为由边的端点全体为顶点集所构成的子图称为由F导出的导出的G的子图，简称的子图，简称G的边导出子图。记为的边导出子图。记为GF。记记G-F表示以表示以E(G)F为边集的为边集的G的支撑子图，的支撑子图，它是从它是从G中删除中删除F中的边所得到的子图。中的边所得到的子图。如如F=e，则记。，则记。边导出子图设F是图G的非空边子集，以F为边集，以F中边的端点30子图图例子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v5e1e2G的支撑子图的支撑子图G-e1,e 2,e 3子图图例v1v2v3v4v5e1e3e2Gv1v2v3v4v31子图图例子图图例2v2v3v4e2G-v 1,v 5 v1v2v5Gv 1,v 2,v 5 v1v2v3v4e1e3e2G e1,e 2,e 3子图图例2v2v3v4e2G-v 1,v 5 v1v2v32径径n顶点顶点vk叫叫W的终点，的终点，n顶点顶点v0 称为称为w的起点，的起点，n顶点顶点vi 叫叫W的内部顶点，的内部顶点，n整数整数k称为称为W的长度。的长度。n在简单图中，径可由顶点序列表示。在简单图中，径可由顶点序列表示。图图G的一个有限的点边交错序列称为从的一个有限的点边交错序列称为从v0到到vk的径；的径；其中其中vi与与v i+1是边是边ei的顶点的顶点;径顶点vk叫W的终点，图G的一个有限的点边交错序列称为从v033路、路、链n如果径如果径W的边不相同，则称的边不相同，则称W为一条链，为一条链，如果如果W顶点互不相同，则称顶点互不相同，则称W是一条路。是一条路。链长是链长是W中边的个数中边的个数k。记路长记路长uvwxyabdefgh|路：路：xcwhyeuav|链：链：wcxdyhwbvgyc路、链如果径W的边不相同，则称W为一条链，如果W顶点互不相同34圈圈(回路回路)n如果径如果径W的起点和终点相同且有正长度，则称它是的起点和终点相同且有正长度，则称它是一个闭径；一个闭径；n如果一条闭链的顶点互不相同，则称它是一个圈如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。（或回路）。n称一个圈是偶圈（奇圈），如果它的圈长是偶数称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。（奇数）。uvwxyabdefgh圈：uavbwhyeuc圈(回路)如果径W的起点和终点相同且有正长度，则称它是一个闭35定理定理n一个图是二分图当且仅当图中不存在奇圈。一个图是二分图当且仅当图中不存在奇圈。定理一个图是二分图当且仅当图中不存在奇圈。36Euler圈圈nEuler圈是指过所有边一次且恰好一次的闭径。圈是指过所有边一次且恰好一次的闭径。nEuler链是指过所有边一次且恰好一次的链。链是指过所有边一次且恰好一次的链。uvwxyabdefghEuler链:ydxcwheuavfygvbwcEuler圈Euler圈是指过所有边一次且恰好一次的闭径。u37图例图例n下例给出了一个图的径，链和路。下例给出了一个图的径，链和路。n径：径：uavfyfvgyhwbvn链：链：wcxdyhwbvgyn路：路：xcwhyeuavn圈：圈：uavbwhyeunEuler链链:ydxcwheuavfygvbwuvwxyabcdefgh图例下例给出了一个图的径，链和路。uvwxyabcdefgh38Euler型型定理定理n定理定理2设设G是连通圈，则是连通圈，则G是是Euler型的充型的充要条件是要条件是G没有奇次数的顶点。没有奇次数的顶点。n推论推论1设设G是一个连通图，则是一个连通图，则G有有Euler链链当且仅当当且仅当G最多有两个奇数次数的顶点。最多有两个奇数次数的顶点。Euler型定理定理2设G是连通圈，则G是Euler型的充39连通性连通性n图图G称为连通的，如果在称为连通的，如果在G的任意两个的任意两个顶点顶点u和和v中存在一条中存在一条(u,v)路。路。|不连通图至少有两个连通分支。不连通图至少有两个连通分支。两点顶点两点顶点u和和v等价当且仅当等价当且仅当u和和v中存在一条中存在一条(u,v)路路w表示表示G的连通分支数。的连通分支数。连通性图G称为连通的，如果在G的任意两个顶点u和v中存在一条40赋权图赋权图对图对图G的每条边的每条边e，赋予一实数，赋予一实数w(e),称为边称为边e的权，的权，可得一赋权图。可得一赋权图。给定赋权图的一个子图给定赋权图的一个子图H，定义，定义H的权为的权为H的所有边的所有边权的总和。权的总和。赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。7.2 最短路问题最短路问题赋权图对图G的每条边e，赋予一实数w(e),称为边e的权，可41赋权图中一条路的权称为路长。赋权图中一条路的权称为路长。在一个赋权图在一个赋权图G上，给定两个顶点上，给定两个顶点u和和 v，所谓，所谓u和和 v最短路是指所有连接顶点最短路是指所有连接顶点u和和 v 的路中路长最的路中路长最短的路；短的路；u和和 v最短路的路长也称为最短路的路长也称为u和和 v的距离。的距离。赋权图中一条路的权称为路长。42n例一个连接例一个连接11个城镇的交通图以及城市个城镇的交通图以及城市u与与v之间的一条最短路。（粗线表示）之间的一条最短路。（粗线表示）uvuv43Dijkstra算法nDijkstra算法的基本思想：算法的基本思想：n设设S是是V的真子集，的真子集，。如果是从如果是从u 0到的最短路，到的最短路，则则，并且，并且P的的 段是最短的段是最短的 路，所以路，所以n并且并且(1)u0u1PDijkstra算法Dijkstra算法的基本思想：(1)u44算法标号算法标号n令令l ij表示从顶点表示从顶点v i到顶点到顶点v j的距离；的距离；d ij表表示连接顶点示连接顶点v I与顶点与顶点v j边长，即边长，即n公式（公式（1）是）是Dijkstra算法的基础。算法的基础。n算法以标号方式进行，每进行一次都增加一算法以标号方式进行，每进行一次都增加一个标号点，直至找到所求的最短路。个标号点，直至找到所求的最短路。算法标号令l ij表示从顶点v i到顶点v j的距离；d 45Dijkstra算法步骤算法步骤nStep0 在点在点v s上标号上标号l ss=0;nStep1 若若v t已标号，转已标号，转Step4;n 否则转否则转Step2;nStep2 令令S表示所有已标号点，表示未标号表示所有已标号点，表示未标号点，计算点，计算l sj，转，转Step3nStep3 令令nStep4 l st是所求的最短路长，是所求的最短路长，f反向追踪找出反向追踪找出所求所求v s-v t最短路最短路.Dijkstra算法步骤Step0 在点v s上标号l s46计算实例计算实例SDBTCEA227414731555求连接求连接S、T的最短路的最短路计算实例SDBTCEA227414731555求连接S、T的47计算实例计算实例1SDBTCEA227414731555求连接求连接S、T的最短路的最短路02计算实例1SDBTCEA227414731555求连接S、T48计算实例计算实例2SDBTCEA227414731555求连接求连接S、T的最短路的最短路0244计算实例2SDBTCEA227414731555求连接S、T49计算实例计算实例3SDBTCEA227414731555求连接求连接S、T的最短路的最短路02447计算实例3SDBTCEA227414731555求连接S、T50计算实例计算实例4SDBTCEA227414731555求连接求连接S、T的最短路的最短路024478计算实例4SDBTCEA227414731555求连接S、T51计算实例计算实例5SDBTCEA227414731555求连接求连接S、T的最短路的最短路02447813L ST=13;S-T最短路为最短路为SABEDT计算实例5SDBTCEA227414731555求连接S、T52实例评述实例评述nDijkstra算法不仅找到了所求最短路，而且算法不仅找到了所求最短路，而且找到了从找到了从S点到其他所有顶点的最短路；这点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。图，即图的一个支撑树。实例评述Dijkstra算法不仅找到了所求最短路，而且找到了53选址问题选址问题n设设G表示一个矿区的交通运输图，矿井表示一个矿区的交通运输图，矿井和之间的里程是；现在需建一个和之间的里程是；现在需建一个矿区煤炭运输站，把运输站设在哪个矿区煤炭运输站，把运输站设在哪个矿井所在地才能使得离运输站距离最矿井所在地才能使得离运输站距离最远的矿井可运输里程最短。这就是最远的矿井可运输里程最短。这就是最简单的选址问题。简单的选址问题。n矿区的交通运输图是一个赋权图，每矿区的交通运输图是一个赋权图，每个矿井是图的一个顶点。个矿井是图的一个顶点。n在赋权图在赋权图G中，定义顶点中，定义顶点u的离距为：的离距为：选址问题设G表示一个矿区的交通运输图，矿井和之间的里程是54中心问题中心问题网络网络G的一个中心是满足下列条件的的一个中心是满足下列条件的G的顶点的顶点u选址问题可化为求选址问题可化为求G的中心问题。的中心问题。求图的中心的算法过程：求图的中心的算法过程：用用Dijkstra算法求出算法求出G的任意两点间的距离；的任意两点间的距离；求出每点的离距求出每点的离距d(v)求满足（求满足（2）的顶点）的顶点v即是中心即是中心（2）中心问题网络G的一个中心是满足下列条件的G的顶点u（2）55实例实例图图7-15给出了一个矿区的交通运输图。应把给出了一个矿区的交通运输图。应把运输站建在哪个矿井才能满足选址要求？运输站建在哪个矿井才能满足选址要求？v3v4v5v2v6v1v763221.531.81.52.5实例图7-15给出了一个矿区的交通运输图。应把运输站建在哪个56n这个问题实际上只需求出这个问题实际上只需求出G的一个中心即可。的一个中心即可。按上面的算法过程，首先利用按上面的算法过程，首先利用Dijkstra算法得算法得到图到图7-15的距离表；再求出每个点的离距，最的距离表；再求出每个点的离距，最后找出离距的最小者后找出离距的最小者v 6就是建运输站的矿井。就是建运输站的矿井。4.8v*=这个问题实际上只需求出G的一个中心即可。按上面的算法过程，首57注注:Dijkstra算法只适用于所有算法只适用于所有ij0的情形，当赋的情形，当赋权有向图中存在负权时，算法失效。如权有向图中存在负权时，算法失效。如v1v2v3 12-3用Dijkstra算法可以得出从算法可以得出从1到到v2的最短路的权是的最短路的权是1，但实际，但实际上从上从1到到v2的最短路是（的最短路是（1，v3，v2），权是），权是-1。注:Dijkstra算法只适用于所有ij0的情形，当赋权58下面介绍具有负权赋权有向图下面介绍具有负权赋权有向图D的最短路的算法。的最短路的算法。不妨假设从任一点不妨假设从任一点vi到任一点到任一点vj都有一条弧（如果在都有一条弧（如果在D中，中，（vi，vj）A，则添加弧（，则添加弧（vi，vj）令）令wij=+）。）。显然，从显然，从vs到任一点到任一点vj的最短路总是从的最短路总是从vs出发到某个点出发到某个点vi，再沿（，再沿（vi，vj）到）到vj的，由前面的结论可知，从的，由前面的结论可知，从vs到到vi的这条路必定是从的这条路必定是从vs到到vi的最短路，所以的最短路，所以d（vs，vj）必满足如下方程：必满足如下方程：下面介绍具有负权赋权有向图D的最短路的算法。不妨假设从任一点59数学建模图论详解图论与网络规划课件606-1-3-283-52-111-1217-3-5例：求例：求1到各点的最短路到各点的最短路6-1-3-283-52-111-1217-3-5例：求161wijv1v2v3v4v5v6v7v8t=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-627.3 最大流问题最大流问题7.3 最大流问题63可行流可行流设设D=(V,A,W)是一个有向网络。是一个有向网络。v s是网络的源点，是网络的源点，v t是网络的汇点。是网络的汇点。设设f是定义在弧集是定义在弧集A上的一个整数函数，如果对所有上的一个整数函数，如果对所有弧弧 a 成立成立(1)并且对所有中间顶点并且对所有中间顶点 v 成立成立(2)则称则称 f 是网络是网络D上的一个可行流。上的一个可行流。其中，其中，f+(v)是流出是流出v 的流量，的流量，f -(v)是流入是流入v的流量的流量。可行流设D=(V,A,W)是一个有向网络。v s是网络的64流量流量条件（条件（1）称为容量限制；即过弧的流量不超过该弧的）称为容量限制；即过弧的流量不超过该弧的容量。容量。条件（条件（2）称为守恒条件，即对于中间点）称为守恒条件，即对于中间点v，流入，流入v的的流量等于流出流量等于流出v的流量。的流量。对于源点对于源点v s和汇点和汇点v t，流出源点，流出源点v s的流量等于流入汇的流量等于流入汇点点v t的流量，称之为流的流量，称之为流 f 的值，记为的值，记为val f.即即流量条件（1）称为容量限制；即过弧的流量不超过该弧的容量。65流值流值流值66例例网络网络D及其一个流量及其一个流量3的可行流的可行流（弧上第一个数字是流量，第二个数字是容量）（弧上第一个数字是流量，第二个数字是容量）vsv1v3v4v2vt1,31,22,22,21,22,31,01,10,1图4.1 Val f=3例网络D及其一个流量3的可行流vsv1v3v4v2vt1,367最大流最大流网络最大流是指给定网络上的流值最大的一个可行流。网络最大流是指给定网络上的流值最大的一个可行流。寻找给定网络的最大流及其有效算法是网络规划的一个寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。重要问题。Ford 与与 Fulkerson 在在1957年提出一个求解网络最大年提出一个求解网络最大流问题的算法，成为流问题的算法，成为Ford Fulkerson 算法。算法。最大流网络最大流是指给定网络上的流值最大的一个可行流。68Ford Fulkerson 算法算法nFord Fulkerson 算法的基本思想是从任算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。行流，依次进行下去，直到一个最大流为止。Ford Fulkerson 算法Ford Fulk69链链n设设P是网络是网络D的一条连接源点的一条连接源点v s和汇点和汇点v t的的链，则链，则P中的弧可分为两类：中的弧可分为两类：n正向弧正向弧弧的方向与弧的方向与P的走向一致；记为的走向一致；记为P+.n反向弧反向弧弧的方向与弧的方向与P的走向相反的走向相反;记为记为P-.注、链不是有向路，链的每一边去掉方向是一条路注、链不是有向路，链的每一边去掉方向是一条路链设P是网络D的一条连接源点v s和汇点v t的链，则P中的70增广链增广链n设设P是网络是网络D的一条连接源点的一条连接源点v s和汇点和汇点v t的链，的链，f 是是网络网络D上的一个可行流上的一个可行流.如果如果P的每一正向弧都是不饱的每一正向弧都是不饱和弧（和弧（），而），而P的每一反向弧的流量都为的每一反向弧的流量都为正（正（）；则称）；则称P是网络是网络D的关于可行流的关于可行流f 的一的一条增广链。简称增广链。条增广链。简称增广链。增广链设P是网络D的一条连接源点v s和汇点v t的链，f71割集割集n设设S、T是网络是网络D的两个顶点子集，且的两个顶点子集，且n定义定义D的一个割集，简称割为的一个割集，简称割为n割集的割量定义为割集的割量定义为n最小割是指割量最小的割最小割是指割量最小的割割集设S、T是网络D的两个顶点子集，且72定定理理对于网络的任意流对于网络的任意流 f 和割和割E(S,Sc)成立成立证明证明 由定义可知由定义可知定理对于网络的任意流 f 和割E(S,Sc)成立73推论推论推论推论1 对于网络的任意流对于网络的任意流 f 和割和割E(S,Sc)，成立，成立推论推论2 设设 f 是网络的一个可行流，是网络的一个可行流，K是网络的一是网络的一个割，如果成立个割，如果成立 则则f 是最大流，是最大流，K是最小割。是最小割。注：注：推论推论2的逆命题也成立，称为最大流最小割定理，是网的逆命题也成立，称为最大流最小割定理，是网络理论的一个重要定理。络理论的一个重要定理。推论推论1 对于网络的任意流 f 和割E(S,Sc)，成74例例n可行流可行流f 与增广链与增广链PnP=v s v1 v2 v tvsv1v3v4v2vt1,31,22.22,21,22,30,11,10,1图4.1 Val f=3例可行流f 与增广链Pvsv1v3v4v2vt1,31,2275定理定理n设设f 是网络是网络D上的一个可行流，则上的一个可行流，则 f 是一个最大流当是一个最大流当且仅当网络且仅当网络D不存在不存在f 的增广链。的增广链。n证明证明 （必要性）（必要性）n 设设f 是一个最大流，假如是一个最大流，假如D中存在中存在f 的增广链的增广链P,则可则可以得到一个流值更大的流以得到一个流值更大的流f 1,使得使得定理设f 是网络D上的一个可行流，则 f 是一个最大流当且仅76证明证明n构造过程如下：构造过程如下：其中其中证明构造过程如下：其中77证明证明n充分性充分性n设网络设网络D不存在不存在f 的增广链，令的增广链，令S表示表示D中可通过用中可通过用不饱和路把源点与之相连的所有顶点集合，不饱和路把源点与之相连的所有顶点集合，Sc表示表示S的余集。则的余集。则n从而从而K=(S,Sc)是是D的割集，进而可得的割集，进而可得nK=(S,Sc)中的弧都是饱和弧，而中的弧都是饱和弧，而 K1=(Sc,S)中的中的弧都是弧都是0流弧，流弧，n否则将产生网络否则将产生网络D 的一条增广链。因此，的一条增广链。因此，f 的流值的流值等于割集等于割集K的割量的割量，所以，所以，f是一个最大流。是一个最大流。证明充分性78算例算例n求下面网络的最大流求下面网络的最大流vsv1v3v4v2vt852879665图4.23定理的证明过程蕴涵着最大流算法定理的证明过程蕴涵着最大流算法算例求下面网络的最大流vsv1v3v4v2vt852879679初始流初始流0n先给网络赋一个初始先给网络赋一个初始0流流f 0 vsv1v3v4v2vt0,80,50,20,80,70,90,60,6图4.2-10,50,3初始流0先给网络赋一个初始0流f 0 vsv1v3v4v2v80寻找增广链寻找增广链1n利用标号法寻找流利用标号法寻找流f 0 的增广链的增广链P0vsv1v3v4v2vt0,80,50,20,80,70,90,60,6图4.2-10,50,3(-,)(+vs,8)(+vs,2)寻找增广链1利用标号法寻找流f 0 的增广链P0vsv1v381寻找增广链寻找增广链2n利用标号法寻找流利用标号法寻找流f 0 的增广链的增广链P0vsv1v3v4v2vt0,80,50,20,80,70,90,60,6图4.2-10,50,3(-,)(+vs,8)(+vs,2)(+v1,5)(+v3,2)寻找增广链2利用标号法寻找流f 0 的增广链P0vsv1v382寻找增广链寻找增广链3n利用标号法寻找流利用标号法寻找流f 0 的增广链的增广链vsv1v3v4v2vt0,80,50,20,80,70,90,60,6图4.2-10,50,3(-,)(+vs,8)(+vs,2)(+v1,5)(+v2,5)(+v3,2)寻找增广链3利用标号法寻找流f 0 的增广链vsv1v3v483寻找增广链寻找增广链4n找到流找到流f 0 的增广链的增广链P0=v s v1 v2 v t，vsv1v3v4v2vt0,80,50,20,80,70,90,60,6图4.2-10,50,3(-,)(+vs,8)(+vs,2)(+v1,5)(+v2,5)(+v3,2)|调增量调增量r=5.寻找增广链4找到流f 0 的增广链P0=v s v1 v84调整流值调整流值2n调整流值得流值为调整流值得流值为5的新可行流的新可行流f 1，vsv1v3v4v2vt5,85,50,20,80,75,90,60,6图4.2-20,50,3调整流值2调整流值得流值为5的新可行流f 1，vsv1v385寻找增广链寻找增广链5n利用标号法寻找流利用标号法寻找流f 1 的增广链的增广链vsv1v3v4v2vt5,85,50,20,80,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+vs,2)寻找增广链5利用标号法寻找流f 1 的增广链vsv1v3v486寻找增广链寻找增广链6n利用标号法寻找流利用标号法寻找流f 1 的增广链的增广链P1vsv1v3v4v2vt5,85,50,20,80,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+vs,2)(+v3,2)(+v3,2)寻找增广链6利用标号法寻找流f 1 的增广链P1vsv1v387寻找增广链寻找增广链7n利用标号法寻找流利用标号法寻找流f 1 的增广链的增广链P1vsv1v3v4v2vt5,85,50,20,80,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+vs,2)(+v3,2)(+v4,2)(+v3,2)寻找增广链7利用标号法寻找流f 1 的增广链P1vsv1v388寻找增广链寻找增广链8n找到流找到流f 1 的增广链的增广链P1=v s v3 v4 v t，vsv1v3v4v2vt5,85,50,20,80,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+vs,2)(+v3,2)(+v4,2)(+v3,2)|调增量调增量r=2.寻找增广链8找到流f 1 的增广链P1=v s v3 v89调整流值调整流值3n调整流值得流值为调整流值得流值为7的新可行流的新可行流f 2，vsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-30,50,3调整流值3调整流值得流值为7的新可行流f 2，vsv1v390寻找流增广链寻找流增广链9n利用标号法寻找流利用标号法寻找流f 2 的增广链的增广链vsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-10,50,3(-,)(+vs,3)寻找流增广链9利用标号法寻找流f 2 的增广链vsv1v3v91寻找流增广链寻找流增广链10n利用标号法寻找流利用标号法寻找流f 2 的增广链的增广链P2vsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+v1,3)寻找流增广链10利用标号法寻找流f 2 的增广链P2vsv192寻找流增广链寻找流增广链11n利用标号法寻找流利用标号法寻找流f 2 的增广链的增广链nP2=v s v1 v3 v2 v t及调增量及调增量r=3.vsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+v1,3)(+v3,3)(+v3,3)寻找流增广链11利用标号法寻找流f 2 的增广链vsv1v393寻找流增广链寻找流增广链12n利用标号法寻找流利用标号法寻找流f 2 的增广链的增广链nP2=v s v1 v3 v2 v t及调增量及调增量r=3.vsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+v1,3)(+v3,3)(+v2,3)(+v3,3)寻找流增广链12利用标号法寻找流f 2 的增广链vsv1v394寻找流增广链寻找流增广链13n找到流找到流f 2 的增广链的增广链nP2=v s v1 v3 v2 v tvsv1v3v4v2vt5,85,52,22,82,75,90,60,6图4.2-10,50,3(-,)(+vs,3)(+v1,3)(+v3,3)(+v2,3)(+v3,3)调增量调增量r=3.寻找流增广链13找到流f 2 的增广链vsv1v3v4v2v95调整流值调整流值4n调整流值得流值为调整流值得流值为10的新可行流的新可行流f 3，vsv1v3v4v2vt8,85,52,22,82,78,93,60,6图4.2-33,50,3调整流值4调整流值得流值为10的新可行流f 3，vsv1v96寻找流增广链寻找流增广链n利用标号法得不出流利用标号法得不出流f 3 的增广链，因此，的增广链，因此，f 3 是给定网络的最大流，流值为是给定网络的最大流，流值为10。n令令S=v s,则则E(S,Sc)是最小割。是最小割。vsv1v3v4v2vt8,85,52,22,82,78,93,60,6图4.2-33,50,3(-,)寻找流增广链利用标号法得不出流f 3 的增广链，因此，f 397Ford Fulkerson 算法算法nStep0 先给网络赋一个初始先给网络赋一个初始0流流f 0;给给vs标标(-,+)n Step1 寻找流寻找流f 的增广链的增广链(1.1)如果所有标号点已经检查且汇点未标号，转如果所有标号点已经检查且汇点未标号，转Step3；n(1.2)找一个已标号但未检查的点找一个已标号但未检查的点v i 做如下检查：做如下检查：n 对每个弧对每个弧e=(v i,v k),如果如果v k 未标号且未标号且n则给则给v k标号标号(+v i,l(k),其中其中)()(),(min)(efewilkl-=Ford Fulkerson 算法Step0 先给网络98Ford Fulkerson 算法算法n对每个对每个 弧弧e=(v k,v i),如果如果v k 未标号且未标号且则给则给v k标号标号(-v i,l(k),其中其中(1.3)若汇点若汇点v t已标号，转已标号，转Step2;否则转否则转(1.1)nStep2 增广网络流增广网络流从源点从源点v s开始依据标号构造增广链开始依据标号构造增广链P，并调整流值，并调整流值，标号的正负表示增加或减少相应弧的流值；擦去所标号的正负表示增加或减少相应弧的流值；擦去所有标号，转有标号，转Step1.nStep3 令令S表示所有已标号点，则得最小割，表示所有已标号点，则得最小割，相应相应流为最大流，结束流为最大流，结束。)(),(min)(efilkl=Ford Fulkerson 算法对每个 弧e=(v k99