图论与网络.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第七章 图论与网络规划,图论概述,图论(Graph Theory)是运筹学中的一个重要分支，主要研究具有某种二元关系的离散系统的组合结构和性质。,如，通信系统、交通运输系统、信息网络系统、生产工艺流程以及军事后勤保障系统等的问题常用图论模型来描述。,网络规划概述,网络规划(Network Programming)是图论与线性规划的交叉学科，具有广泛的应用背景，比如，最短路问题、最小树问题、最大流问题、最优匹配问题等。,七桥问题,七桥问题图形,原 理 及 方 法,七桥问题是图论中的著名问题。1736年，Euler巧妙,地将此问题化为图的不重复一笔画问题，并证明了,该问题不存在肯定回答。原因在于该图形有顶点连,接奇数条边。,7、1 图的基本概念,一个图(Graph)定义为三元有序组,G,=(,V,(,G,),E,(,G,)，,V,(,G,)是图的顶点集合，,E,(,G,),是,图,的边集合，,记,设,G,是一个图，,图,G的几何实现,图的几何实现,一个图可用一个几何图形表示,称为图的几何实现，其中,每个顶点用点表示，,每条边用连接端点的线表示。,图的几何实现有助与我们直观的了解图的许多性质。,说明,一个图的几何实现并不是唯一的；表示顶点的点和表示边的线的相对位置并不重要，重要的是图形描绘出,边与顶点之间保持的相互关系,。,我们常常把一个图的图形当作这个抽象图自身.,并称图形的点为顶点,图形的线为边，,图论中大多数概念是根据图的表示形式提出的，例如：顶点、边、多重边、环、路、圈、树等。,几何实现图例,在一个图的几何实现中，两条边的交点可能不是图的顶点。例如下图 中，它共有4个顶点，6条边；而,e,3,与,e,4,的交点不是这个图的顶点。,平面图,一个图称为平面图，如它有一个平面图形，使得边与边仅在,顶点相交。下图就是一个平面图，因为它可以有下面的图形。,基本概念,端点重合为一点的边称为,环,。,连接同一对顶点的多条边称为,多重边,。,在右图中，,e,5,是一个环，,e,1,与,e,2,是多重边，,v,1,和,e,1,e,2,e,3,是关联的，,v,1,与,v,2,v,3,是邻接的。,邻接矩阵,设,G,是一个图，,G,=(,V,(,G,),E,(,G,),，定义图,G,的邻接矩阵,A,(,G,),=(,a,ij,),为,m,m,矩阵,a,ij,是顶点,v,i,与边,v,j,相邻接的边数。,其中,关联矩阵,设,G,是一个图，,G,=(,V,(,G,),E,(,G,),定义图,G,的关联矩阵,M,=(,m,ij,)为,m,n,矩阵；,其中,m,ij,是顶点,v,i,与边,e,j,相关联的次数，,取值可能为0、1、2。,注,图的邻接矩阵比它的关联矩阵小的多，因而图常常以其邻接矩阵的形式存贮与计算机中。,关联矩阵和邻接矩阵统称图的矩阵表示。,顶点的度,设,G,是一个图，,G,=(,V,(,G,),E,(,G,)，,定义图,G,的顶点,v,的度为与顶点,v,相关联的边数，记作,d,(,v,),例,称度为奇数的顶点为奇点；,称度为偶数的顶点为偶点；,例,2,2,2,2,2,2,2,4+3+3+4=14=27,关联矩阵性质,图,G,的关联矩阵,M,=(,m,ij,),为,m,n,矩阵；则每行元,素之和等于相应顶点的度；每列元素之和等于2。,因此，,图G的关联矩阵,M,所有元素之和既等于所有顶点的度之和，又等于边数的2倍。,定理设G是一个图，则,推论,图中奇点的数目为偶数。,证明,记,简单图,一个图称为,简单图,，如果,它既没有环也没有多重边,。,下图是简单图。,本书只限于讨论有限简单图，,即顶点集与边集都是有限集的图。,u,1,u,2,u,3,u,4,f,1,f,2,f,6,f,3,f,5,f,4,只有一个顶点的图称为,平凡图,；,边集是空集的图称为,空图,。,同构,称,G,和,H,是同构的，记为，,使得,给定两个图,如果存在两个一一对应,同构图例,图G与图H是同构的。,v,1,v,2,v,3,v,4,u,1,u,2,u,3,u,4,G,H,e,6,e,4,e,2,e,1,e,3,e,5,f,1,f,2,f,6,f,3,f,5,f,4,完全图,K,n,完全图是每一对不同顶点都恰有一边的简单图；,具有n个顶点的完全图记为,K,n.,K,5,二分图,二分图是一个简单图，其顶点集合可分划成两个子集,X,与,Y,，使得每条边的一个端点在,X,，另一个端点在,Y,;,(,X,Y,),也称为图的二分划。,x1,x2,x3,y1,y2,y3,完全二分图,完全二分图是具有二分划,(,X,Y,),的二分图，并且,X,的每个顶点与,Y,的每个顶点都相连；记为,K,m,n,，,其中,K,3,3,特殊图例,K,5,K,3,3,都是极小的非平面图,子图,称图,H,是图,G,的子图，,图G及其基本图,称,H,是,G,的,支撑子图,，,如果,称,H,是,G,的真子图,，,若,如果,表示关联函数,记为,在,H,的限制。,顶点导出子图,设,W,是图,G,的一个非空顶点子集,以,W,为顶点集，以二端点均在,W,中的边的全体为边集的子图称为由,W,导出的,G,的子图，简称导出子图，记为,G,W,。,导出子图,G,V,-,w,记为,G,-,W,，即,它是从,G,中删除,W,中顶点以及与这些顶点相关联的边所得到的子图。,如果,W,仅含一个顶点,v,，则把 简记为。,边导出子图,设,F,是图,G,的非空边子集，以,F,为边集，以,F,中边的端点全体为顶点集所构成的子图称为由,F,导出的,G,的子图，简称,G,的边导出子图。记为,G,F,。,记,G,-,F,表示以,E,(,G,),F,为边集的,G,的支撑子图，它是从,G,中删除,F,中的边所得到的子图。,如,F,=,e,，则记。,子图图例,v,1,v,2,v,3,v,4,v,5,e,1,e,3,e,2,G,v,1,v,2,v,3,v,4,v,5,G,的支撑子图,G,-,e,1,e,2,e,3,子图图例2,v,2,v,3,v,4,e,2,G,-,v,1,v,5,v,1,v,2,v,5,G,v,1,v,2,v,5,v,1,v,2,v,3,v,4,e,1,e,3,e,2,G,e,1,e,2,e,3,v,1,v,2,v,3,v,4,v,5,e,1,e,3,e,2,G,途径,顶点,v,k,叫,W,的终点，,顶点,v,0,称为,W,的起点，,顶点,v,i,叫,W,的内部顶点，,整数,k,称为,W,的长度。,在简单图中，径可由顶点序列表示。,图G的一个有限的点边交错序列称为从,v,0,到,v,k,的途径。,其中,v,i,与,v,i,+1,是边,e,i,的顶点;,路、,链,如果径,W,的边不相同，则称,W,为一条链，,如果,W,顶点互不相同，则称,W,是一条路。,链长是,W,中边的个数,k,。,记路长,u,v,w,x,y,a,b,d,e,f,g,h,路：,xcwhyeuav,链：,wcxdyhwbvgy,c,圈(回路),如果途径,W,的起点和终点相同且有正长度，则称它是一个闭途径；,如果一条闭链的顶点互不相同，则称它是一个圈（或回路）。,称一个圈是偶圈（奇圈），如果它的圈长是偶数（奇数）。,圈：uavbwhyeu,u,v,w,x,y,a,b,d,e,f,g,h,c,定理,一个图是二分图当且仅当图中不存在奇圈。,Euler圈,Euler圈是指过所有边一次且恰好一次的,闭途径,。,Euler链是指过所有边一次且恰好一次的链。,Euler链:ydxcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,图例,下例给出了一个图的径，链和路。,径：,uavfyfvgyhwbv,链：,wcxdyhwbvgy,路：,xcwhyeuav,圈：,uavbwhyeu,Euler链:,ydxcwheuavfygvbw,u,v,w,x,y,a,b,d,e,f,g,h,c,Euler型,定理,定理2,设,G,是连通圈，则,G,是Euler型的充要条件是,G,没有奇次数的顶点。,推论1设,G,是一个连通图，则,G,有Euler链当且仅当,G,最多有两个奇数次数的顶点。,连通性,图,G,称为连通的，如果在,G,的任意两个顶点,u,和,v,中存在一条,(,u,v,),路。,不,连通图至少有两个连通分支。,两点顶点,u,和,v,等价当且仅当,u,和,v,中存在一条(,u,v,)路。,表示,G,的连通分支数。,7.2,最短路问题,Dijkstra,算法,求任意两点的最短路算法,-Floyd,算法,求带负权网络图的最短路的算法,用线性规划求最短路,赋权图,给定赋权图的一个子图,H,，定义,H,的权为,H,的所有边权的总和。,对图,G,的每条边,e,，赋予一实数,(,e,),，称为边,e,的权，可得一,赋权图。,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,赋权图中一条路的权称为路长。,在一个赋权图,G,上，给定两个顶点,u,和,v,，所谓,u,和,v,最短,路是指所有连接顶点,u,和,v,的路中路长最短的路；,u,和,v,最短路的路长也称为,u,和,v,的距离。,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,如何求从,u,到,v,的,最短路的长？,Dijkstra算法的基本思想：,(1),u,0,u,1,P,设,S,是,V,的真子集，,如果 是从,u,0,到的最短路，,则，并且,P,的 段是最短的,路，所以,算法标号,令,d,ij,表示连接顶点,v,i,与顶点,v,j,边上的权，即,(1),公式（1）是Dijkstra算法的基础。,定义结点,v,j,的标号为,始点的标号为,0,-,表明这个点前面没有点。,结点,v,j,的标号分为两种：,临时性标号和永久性标号,。如果找到一条更短的路，临时性标号即被修改，如果找不到一条更短的路，临时性标号即被改为永久性标号。,Step0 令,始点的标号为,0,-.令,i,=1,Step,i,(a),对于由结点,i,可达的还没有永久性标号的结点,j,，,计算其,临时性标号,l,i,+,d,ij,i,（,d,ij,0,）,.,如果,j,已经通过另一个结点,k,标号为,l,j,k,且,l,i,+,d,ij,l,j,则用,l,i,+,d,ij,i,取代,l,j,k,。,(b)如果所有的结点都是永久性标号，停止。否则选择最小的临时性标号,l,r,s,。令,i,=,r,，返回,Step,i,.,计算实例,求连接S、T的最短路,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,l,ST,=13;S-T最短路为,SABEDT,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,实例评述,Dijkstra算法不仅找到了所求最短路，而且找到了从S点到其他所有顶点的最短路；这些最短路构成了图的一个连通无圈的支撑子图，即图的一个支撑树。,S,D,B,T,C,E,A,7,1,2,2,4,4,7,3,1,5,5,5,0,5，s,4，s,2，s,2，s,9，A,4，A,4，s,4，A,8，C,7，B,7，B,8，E,14，E,8，E,13，D,注:,Dijkstra算法只适用于所有,w,ij,0的情形，当赋权有向图中存在负权时，算法失效。如,v,1,v,2,v,3,1,2,-3,用Dijkstra算法可以得出从,v,1,到,v,2,的最短路的权是1，但实际上从,v,1,到,v,2,的最短路是（,v,1,，,v,3,，,v,2,），权是-1。,下面介绍具有负权赋权有向图,D,的最短路的算法。,不妨假设从任一点,v,i,到任一点,v,j,都有一条弧（如果在,D,中，（,v,i,，,v,j,）,A,，则添加弧（,v,i,，,v,j,）令,w,ij,=+）。,显然，从,v,s,到任一点,v,j,的最短路总是从,v,s,出发到某个点,v,i,，再沿（,v,i,，,v,j,）到,v,j,的，由前面的结论可知，从,v,s,到,v,i,的这条路必定是从,v,s,到,v,i,的最短路，所以,d,（,v,s,，,v,j,）必满足如下方程：,6,-1,-3,-2,8,3,-5,2,-1,1,1,-1,2,1,7,-3,-5,例：求,v,1,到各点的最短路。,w,ij,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,t,=1,t,=2,t,=3,t,=4,v,1,0,-1,-2,3,0,0,0,0,v,2,6,0,2,-1,-5,-5,-5,v,3,-3,0,-5,1,-2,-2,-2,-2,v,4,0,2,3,-7,-7,-7,v,5,-1,0,1,-3,-3,v,6,1,0,-1,7,-1,-1,-1,v,7,-1,-3,0,5,-5,-5,v,8,-5,0,6,6,例一个连接11个城镇的交通图以及城市,u,与,v,之间的一条最短路。（粗线表示）,u,v,u,v,求任意两点的最短路算法-Floyd算法,这种算法用一个,n,阶方阵来表示一个,n,-结点网络.矩阵中的(,i,j,)-元,d,ij,表示从,i,到,j,边上的权,即,i,j,k,Floyds algorithm 的基本思想：给定结点,i,j,和,k,，若有如下三角形，且 ，则从,i,经过,k,到,j,比直接到,j,所经过路线短。,此时用,i,k,j,代替,i,j,最好.-,三角形运算,1,2,4,5,3,3,5,4,6,15,10,1 2 3 4 5,1,2,3,4,5,3,10,3,5,10,6,15,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,4,5,1,3,4,5,1,2,4,5,1,2,3,5,1,2,3,4,1 2 3 4 5,1,2,3,4,5,3,10,3,5,10,6,15,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,4,5,1,3,4,5,1,2,4,5,1,2,3,5,1,2,3,4,1 2 3 4 5,1,2,3,4,5,3,10,3,13,5,10,13,6,15,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,4,5,1,1,4,5,1,1,4,5,1,2,3,5,1,2,3,4,1 2 3 4 5,1,2,3,4,5,3,10,3,13,5,10,13,6,15,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,4,5,1,1,4,5,1,1,4,5,1,2,3,5,1,2,3,4,1,2,3,4,5,3,10,8,3,13,5,10,13,6,15,8,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,2,5,1,1,4,5,1,1,4,5,2,2,3,5,1,2,3,4,1 2 3 4 5,1,2,3,4,5,3,10,8,3,13,5,10,13,6,15,8,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,2,5,1,1,4,5,1,1,4,5,2,2,3,5,1,2,3,4,1,2,3,4,5,3,10,8,25,3,13,5,28,10,13,6,15,8,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,2,3,1,1,4,3,1,1,4,5,2,2,3,5,1,2,3,4,1 2 3 4 5,1 2 3 4 5,1,2,3,4,5,3,10,8,25,3,13,5,28,10,13,6,15,8,5,6,4,4,1 2 3 4 5,1,2,3,4,5,2,3,2,3,1,1,4,3,1,1,4,5,2,2,3,5,1,2,3,4,1 2 3 4 5,1,2,3,4,5,3,10,8,12,3,11,5,9,10,11,6,10,8,5,6,4,12,9,10,4,1 2 3 4 5,1,2,3,4,5,2,3,2,4,1,4,4,4,1,4,4,4,2,2,3,5,4,4,4,4,1 2 3 4 5,1,2,3,4,5,3,10,8,12,3,11,5,9,10,11,6,10,8,5,6,4,12,9,10,4,1 2 3 4 5,1,2,3,4,5,2,3,2,4,1,4,4,4,1,4,4,4,2,2,3,5,4,4,4,4,1 2 3 4 5,1,2,4,5,3,3,5,4,6,15,10,1245,用线性规划求最短路,1,2,4,5,3,100,15,50,10,60,30,求从1到2的最短路,20,7.3 树,树（,tree,）,是一个不包含圈的简单连通图。,具有,k,个连通分支的不包含圈的图称为,k,-,树，或森林。,下图列出了具有六个顶点的不同构的树。从中可以看出，,图中的每棵树都只有,5,条边，并且至少有,2,个顶点的次数是,1,。,性质,1设,G,是一棵树，则：,G,中任意两点均有唯一的路连接。,2,G,的边数等于顶点数减1，即,3 若,G,不是平凡图，则,G,至少有两个次数为1的顶点。,定理1,设,G,是一个简单图，则下列六个命题是等价的。,G,是一棵树。,无圈且,m,=,n,-1,。,G,连通且,m,=,n,-1,。,G,连通并且每条边都是割边。,G,中任意两点都有唯一的路相连。,G,无圈，但在任意一对不相邻的顶点之间加连一条边，则构成唯一的一个圈。,支撑树,图,G,的支撑树是,G,的支撑子图，并且是一棵树。,每个连通图都有支撑树,支撑树也称为连通图的极小连通支撑子图。,很显然，一个连通图只要本身不是一棵树，它的支撑树就不止一个。,定理,定理4设,T,1,和,T,2,是,G,的两个支撑树，令,则,T,1,经过,k,次迭代后可得到,T,2,。,定理,2,设,G,是一个连通图，,T,是,G,的一棵支撑树，,e,是,G,的一条不属于,T,的边，则,T,+,e,含有,G,的唯一圈。,定理,3,设,T,是连通图,G,的一棵支撑树，,e,是,T,的任意一条边，则：,T,（1）不包含,G,的割集,（2）包含,G,的唯一的割集。,最小树,定理5设,T,是,G,的一个支撑树，则,T,是,G,的最小树的充分,必要条件为对任意边,设,G,是一个赋权图，,T,为,G,的一个支撑树。定义,T,的权为：,G,中权最小的支撑树称为,G,的最小树。,定理6,设,T,是,G,的支撑树，则,T,是,G,的最小树的充分必要条件为对任意边 ，,其中 为,G,的唯一割集。,最小树算法-1-贪心算法,Kruskal在1965年提出一种求最小树的所谓贪心算法。,算法步骤如下,Step0,把边按权的大小从小到大排列得：,置,Step1 若 ，则停，此时,G,S,即为所求的最小树；,否则，转向Step2。,Step2 如果,G,S,+,e,j,不构成回路，则令,转向Step1；否则，令,j,=,j,+1,转向Step2。,算例,图7-18展示了利用Kruskal算法求最小树的迭代过程。,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-18,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-18-1,评注,Kruskal算法的总计算量为 ，有效性不太好。,求最小树的一个好的算法是Dijkstra于1959年提出的，算法的实质是在图的 个独立割集中，取每个割集的一条极小边来构成最小树。,最小树算法-2-Dijkstra算法,Step0 置,Step1 取,置,Step2 若 ，则停止；,否则，置 ，返回Step1,算例2,图7-19展示了利用Dijkstra算法求最小树的迭代过程。,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-19,利用Dijkstra算法求最小树的迭代过程。,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-19-1,破圈法是Dijkstra算法的对偶算法。最适合于图上作业。尤其是当图的顶点数和边数比较大时，可以在各个局部进行。Step1 若,G,不含圈，则停止；否则在,G,中找一个圈,C,，取圈,C,的一条边,e,，满足,最小树算法-3-破圈法,Step2：置,G,=,G,-,e,，返回Step1。利用破圈法求图7-19的最小树的过程如图7-20所示。,算例3,图7-20展示了利用破圈法求最小树的迭代过程。,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-20,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,图7-20-1,评注,上述算法都可以在图上进行。为了便于计算机计算，下面介绍Dijkstra的表上算法。,给定一个赋权图,G,，可以相应地定义一个邻接矩阵,A,=(,w,ij,)，其中,w,ij,是连接顶点,v,i,和,v,j,的权;若,v,i,v,j,不是,G,的边，则令,w,ij,等于无穷大。,Step0：画掉第一列的所有元素（例如打上 ），并在第一行的每个元素下面画一横线。,Step1：在画横线的元素中找一个最小的,w,ij,，用圆圈起来，把第,j,列其他元素画掉，并把第,j,行没有画掉的元素画上横线。,Step2：如果还有没有圈起来和没有画掉的元素，则返回Step1；否则，结束。这时圈起来的元素代表最小树的边，所有圈起来的元素之和就是最小树的权。,最小树算法-4-表上作业法,算例,用表上作业法求图7-19的最小树的过程为：,最小对的权=1+2+3+2=8。,v,1,v,2,v,4,v,5,v,3,1,2,2,4,4,3,4,2,最小连接问题,作为最小树的应用问题之一是所谓的连接问题：欲建造一个连接若干城镇（矿区或工业区）的铁路网，给定城镇,i,和,j,之间直通线路的造价为,c,ij,，试设计一个总造价最小的铁路运输图。,把每个城镇看作是具有权,c,ij,的赋权图,G,的一个顶点。显然连接问题可以表述成：在赋权图,G,中，求出具有最小权的支撑树,。,7.4 最大流问题,v,s,v,1,v,3,v,4,v,2,v,t,3,2,2,2,2,3,1,1,1,网络流图,设,D=,(,V,A,W,),是一个有向网络。,v,s,是网络的源点，,v,t,是网络的汇点。,弧上的数字是允许通过的最大流量,。,可行流,设,f,是定义在弧集,A,上的一个函数，如果对所有弧,a,成立,并且对所有,中间顶点,v,成立,其中，,f,+,(,v,),是流出,v,的流量，,f,-,(,v,),是流入,v,的流量。,则称,f,是网络,D,上的一个可行流。,2,1,v,s,v,1,v,3,v,4,v,2,v,t,3,1,2,1,2,2,2,1,3,2,1,0,1,0,1,1,-容量限制,-守恒条件,流值,对于源点,v,s,和汇点,v,t,，流出源点,v,s,的流量等于流入汇点,v,t,的流量，称之为流,f,的值，记为,val f,。,即,v,s,v,1,v,3,v,4,v,2,v,t,3,1,2,1,2,2,2,1,2,1,3,2,1,0,1,0,1,1,val,f,=3,最大流,网络最大流是指给定网络上的流值最大的一个可行流。,寻找给定网络的最大流及其有效算法是网络规划的一个重要问题。,Ford 与 Fulkerson 在1957年提出一个求解网络最大流问题的算法，称为Ford Fulkerson 算法。,割集,设,S,是网络的顶点子集，且,割集的容量定义为,最小割是指容量最小的割。,定义,D,的一个割集，简称割为,v,s,v,1,v,3,v,4,v,2,v,t,3,2,2,2,2,3,1,1,1,定理1,对于网络的任意流,f,和割 成立,证明 由定义可知,推论1,对于网络的任意流,f,和割,，,成立,v,s,v,1,v,3,v,4,v,2,v,t,3,2,2,2,2,3,1,1,1,注：推论2的逆命题也成立，即推论中的等式永远成立。称为最大流最小割定理，是网络理论的一个重要定理。,则,f,是最大流，,K,是最小割。,如果成立,推论2,设,f,是网络的一个可行流，,是网络的一个割，,链、正向弧、反向弧,设,P,是网络,D,的一条链，则,P,中的弧可分为两类：,正向弧弧的方向与,P,的走向一致；记为,P,+,。,反向弧弧的方向与,P,的走向相反,;,记为,P,-,。,网络,D,的连接源点,v,s,和汇点,v,t,的路。,v,s,v,1,v,3,v,4,v,2,v,t,3,2,2,2,2,3,1,1,1,增广链,设,P,是网络,D,的一条连接源点,v,s,和汇点,v,t,的链，,f,是网络,D,上的一个可行流.,如果,P,的每一正向弧都是,不饱和弧,，,而,P,的每一反向弧的流量都为正,；,则称,P,是网络,D,的关于可行流,f,的一条可增广链。简称增广链。,可增广链上流量可以增加。,v,s,v,1,v,3,v,4,v,2,v,t,3，,1,2,1,2,2,2,2,2,1,3,2,1,0,1,1,1,0,定理2,设,f,是网络,D,上的一个可行流，则,f,是一个最大流当且仅当网络,D,不存在,f,的增广链。,证明 （必要性）,设,f,是一个最大流，假如,D,中存在,f,的增广链,P,则可以得到一个流值更大的流,f,1,使得,构造过程如下：,其中,证明,充分性,设网络,D,不存在,f,的增广链。定义,S,如下：,从而 是,D,的割集，进而可得,中的弧都是饱和弧，而 中的弧都是,0,流弧，,否则将产生网络,D,的一条增广链。因此，,f,的流值等于割,集,的割量,，所以，,f,是一个最大流。,定理3,在任何网络流图中，最大流的值等于最小割的容量。,（最大流最小割定理）,Ford Fulkerson 算法,Ford Fulkerson 算法的基本思想是从任意一个可行流出发，寻找流的增广链，并在这条增广链上调整流值，进而得到一个新可行流，依次进行下去，直到一个最大流为止。,定理的证明过程蕴涵着最大流算法,算例,求下面网络的最大流,v,s,v,1,v,3,v,4,v,2,v,t,8,5,2,8,7,9,6,6,5,图4.2,3,初始0流,先给网络赋一个初始0流,f,0,图4.2-1,v,s,v,1,v,3,v,4,v,2,v,t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+v,s,8),(+v,s,2),(-,),寻找增广链1,v,s,v,1,v,3,v,4,v,2,v,t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,v,s,v,1,v,3,v,4,v,2,v,t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+v,s,8),(+v,s,2),(-,),(+v,1,5),(+v,3,2),寻找增广链2,v,s,v,1,v,3,v,4,v,2,v,t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+v,s,8),(+v,s,2),(-,),(+v,1,5),(+v,3,2),(+v,2,5),寻找增广链3,寻找增广链4,找到流,f,0,的增广链,P,0,=,v,s,v,1,v,2,v,t,.,v,s,v,1,v,3,v,4,v,2,v,t,8,0,5,0,2,0,8,0,7,0,9,0,6,0,6,0,5,0,3,0,(+,v,s,8),(+,v,s,2),(-,),(+,v,1,5),(+,v,3,2),(+,v,2,5),增量,=5.,调整流值2,调整流值得流值为,5,的新可行流,f,1,，,v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+,v,s,3),(+,v,s,2),(-,),v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+,v,s,3),(+,v,s,2),(-,),(+,v,3,2),(+,v,3,2),v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+,v,s,3),(+,v,s,2),(-,),(+,v,3,2),(+,v,3,2),(+,v,2,2),增量,=2.,v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,0,8,0,7,0,9,5,6,0,6,0,5,0,3,0,(+,v,s,3),(+,v,s,2),(-,),(+,v,3,2),(+,v,3,2),(+,v,2,2),找到流,f,1,的增广链,P,0,=,v,s,v,3,v,2,v,t,，,调整流值3,调整流值得流值为,7,的新可行流,f,2,，,v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,2,8,0,7,0,9,7,6,0,6,0,5,2,3,0,v,s,v,1,v,3,v,4,v,2,v,t,8,5,5,5,2,2,8,0,7,0,9,7,6,0,6,0,5,2,3,0,(+,v,s,3),(+,v,1,3),(-,),(+,v,3,3),(+,v,3,3),(+,v,2,2),增量,=2.,v,s,v,1,v,3,v,4,v,2,v,t,8,7,5,5,2,2,8,0,7,0,9,9,6,2,6,0,5,4,3,0,v,s,v,1,v,3,v,4,v,2,v,t,8,7,5,5,2,2,8,0,7,0,9,9,6,2,6,0,5,4,3,0,(+,v,s,1),(+,v,1,1),(-,),(+,v,3,1),(+,v,3,1),(+,v,4,1),增量,=1.,v,s,v,1,v,3,v,4,v,2,v,t,8,8,5,5,2,2,8,1,7,1,9,9,6,3,6,0,5,4,3,0,v,s,v,1,v,3,v,4,v,2,v,t,8,8,5,5,2,2,8,1,7,1,9,9,6,3,6,0,5,4,3,0,(-,),寻找增广链,利用标号法得不出流,f,3,的增广链，因此，,f,3,是给定网络的最大流，流值为,10,。,令,S=,v,s,则 是最小割。,Ford Fulkerson 算法,Step0,先给网络赋一个初始,0,流,f,0,;,给,v,s,标,(-,+),Step1,寻找流,f,的增广链,(1.1),如果所有标号点已经检查且汇点未标号，转,Step3；,(1.2),找一个已标号但未检查的点,v,i,做如下检查：,对每个弧,e,=(,v,i,v,k,),如果,v,k,未标号且,),(,),(,),(,min,),(,e,f,e,c,i,l,k,l,-,=,则给,v,k,标号(+,v,i,l,(,k,),其中,Ford Fulkerson 算法,对每个 弧,e,=(,v,k,v,i,),如果,v,k,未标号且,则给,v,k,标号,(-,v,i,l,(,k,),其中,),(,),(,min,),(,e,f,i,l,k,l,=,Step2 增广网络流,从源点,v,s,开始依据标号构造增广链,P,，并调整流值，,标号的正负表示增加或减少相应弧的流值；擦去所,有标号，转Step1.,(1.3)若汇点,v,t,已标号，转Step2;否则转(1.1).,Step3,令S表示所有已标号点，则得最小割，,相应流为,最大流，结束。,1,2,3,5,4,6,8,5,2,8,7,9,6,6,5,3,Linear Programming of Maximal Flow Mode,7、5 对集,给定一个图G及G的一个边子集M，称M是G的一个,对集,(Matching),如果M中任意两条边都不是相邻的。,有人也将一个对集称为一个,匹配,，因为对集M中每条边的两个端点由M配了对。,图G的一个顶点,v,称为M饱和点，如果,v,与M中的一条边是关联的；否则称,v,是M不饱和点。,对集M称为,完美对集,，如果G的每个顶点都是M饱和点。,图例1,v,7,v,6,v,1,v,8,v,4,v,3,v,2,v,5,图7-21 图的一个完美对集,M=,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,最大对集,对集M称为G的一个,最大对集,，如果G的数目，也叫M的基数，因此，最大对集也称为最大基数对集。,每个完美对集都是最大对集。图7-21指出了两个图的最大对集和完美对集。其中（a）中粗线表示最大对集，（b）中粗线表示完美对集。,图例2,v,7,v,6,v,1,v,8,v,4,v,3,v,2,v,5,图7-21 图的一个最大对集,M=,v,6,v,7,v,1,v,8,v,3,v,4,增广路,设M是G的一个对集，G的一条M交错路是指路中的边在M和E/M中交错出现的路。,一条M交错路称为,M增广路,，如果它的起点和终点都是M不饱和点。,在图7-21（a）中,v,2,v,6,v,7,v,1,v,8,v,5,是一条M增广错路。,v,7,v,6,v,1,v,8,v,4,v,3,v,2,v,5,图7-21（a）,定理,1,Berge,定理,设,M,是,G,的一个对集，则,M,是最大对集的充要条件为,G,不包含,M,增广路。,二分图的对集,设G是具有二分划（X，Y）的二分图，希望寻找M的一个对集，使它饱和X的每个顶点。由Hall于1935年给出存在这种对集的条件。,设S是图G的一个顶点子集，定义S在G中的,邻集,，记为N（S），是与S的顶点邻接的G的所有顶点的集合。,定理2,(Hall),设G是具有二分划（X，Y）的二分图，则G存在一个饱和X的对集M 的充要条件是对X的所有子集S成立,对集的构造,X,Y,S,T,=,N,(,S,),u,图7-22,定理证明过程中，S和T的构造见图7-22。,推论1,推论1,设G是一个,k,正则二分图，,k,是正整数，则G有一个完美对集。,推论,1,也称为婚姻定理：在一个团体中，如果每位姑娘恰好认识,k,位小伙子，而每位小伙子也恰好认识,k,位姑娘，那么每位姑娘能够和她认识的一位小伙子结婚，并且每位小伙子也能和他认识的一位姑娘结婚。,覆盖,图G的一个,覆盖,是指G的顶点子集K，使得G的每条边都至少有一个端点在K中。,v,7,v,6,v,1,v,8,v,4,v,3,v,2,v,5,图7-21 图的一个对集M与覆盖K,