第10章_图与网络分析(清华教材).ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第,10,章图与网络分析,第一节图论的基本概念（,1,）,引言,十八世纪的哥尼斯堡城中流过一条河（普雷,.,格尔河），河上有,7,座桥连接着河的两岸和河中的两个小岛。当时那里的人们热衷于这样一个游戏：一个游者怎样才能一次连续走过这,7,座桥，回到原出发点，而每座桥只允许走一次。没有人想出走法，又无法说明走法不存在，这就是著名的“,哥尼斯堡,7,桥,”难题。,第一节图论的基本概念（,2,）,“,哥尼斯堡,7,桥”,难题最终在,1736,年由数学家,Euler,的一篇论文给予了完满的解决，这是图论的第一篇论文。在后来的两百年间图论的发展是缓慢的，直到,1936,年匈牙利数学家,O.Knig,写出了,图论的第一本专著,有限图与无限图的理论,。,在图论的发展过程中还有两位著名科学家值得一提，他们是,克希霍夫,和,凯莱,。克希霍夫在研究,电网络,时对图的独立回路理论作出了重要的贡献，而化学家凯莱在对,碳氢化合物的同分异构体的数量,进行计数时推动了图论中树的计数问题的研究。,第一节图论的基本概念（,3,）,图论的历史上最具有传奇色彩的问题也许要数著名的,“四色猜想”,了,历史上许许多多数学猜想之一。,它描述对一张地图着色的问题，曾经有一位数学家这样说：“对于这个问题，一位数学家可以用不到五分钟的时间向马路上任何一位行人讲述清楚它，然后，两人都明白这一问题，但是，两人都无能为力。”,幸运的是,在,1970s,终于由美国的,两位数学家借助大型计算机将其证明了。,第一节图论的基本概念（,4,）,定义：,有序二元组,G=(V,E),称为一个,图，其中,(1),V=,v,1,v,2,v,n,是有穷非空集，称为顶点集，,其中的元素叫图,G,的顶点,.,(2),E=e,ij,称为边集，其中的元素叫图,G,的边,.,若,e,ij,=V,i,V,j,是个无序二元组，则图,G,是个无向图,则图为右图形式：,例,1,设,G=(V,E,),，其中,V=,v,1,v,2,v,3,v,4,，,E=,e,1,e,2,e,3,e,4,e,5,第一节图论的基本概念（,5,）,端点：,若,e,ij,=V,i,V,j,，,则称,e,ij,连接,V,i,和,V,j,点,V,i,和,V,j,称为,e,ij,的,端点,一条边的端点称为与这条边,关联,例,1,设,G=(V,E,),，其中,V=,v,1,v,2,v,3,v,4,，,E=,e,1,e,2,e,3,e,4,e,5,点邻接的：,与同一条边关联的两个端点称为,邻接的,第一节图论的基本概念（,4,）,常用术语,：,(1),端点相同的边称为,环,(4),边和它的端点称为,互相关联的,(5),既没有环也没有多重边的图，称为,简单图,(2),若一对顶点之间有两条以上的边联结，,则这些边称为,重边,(3),有边联结的两个顶点称为,相邻的顶点,，,有一个公共端点的边称为,相邻的边,(6),一个没有环但允许多重边的图，称为多重,图,第一节图论的基本概念（,5,）,顶点的次数,:,(1),在无向图中，与顶点,v,关联的边的数目（环算两,次）称为,v,的次数，,记为,d(v),(2),悬挂点：次为,1,的点。,悬挂边：悬挂点的关联边。,孤立点：次为零的点。,第一节图论的基本概念（,6,）,定理,1,:,定理,2,任何图中奇次顶点的总数必为偶数,链：,如果图中的某些点、边可以排列成点和边的,交错序列，则称此为一条链。,圈：,如一条链中起点和终点重合，则称此为一条圈。,初等链（圈）：,如果链（圈）中点都是不同的，,就称之为初等链（圈）。,简单链（圈）：,如果链（圈）中边均不相同，,就称之为初等链（圈）。,连通图：,如果图中的任意两点之间至少存在一条链，,则称图为连通图，否则为不连通图。,支撑子图：,给了一个图,G=(V,E),如果图,G,=(V,E),使,V=V,及,E,包含于,E,则称,G,是,G,的一个支撑子图。,基础图：,设给了一个有向图,D=(V,A),从,D,中去掉所有弧,上得箭头就得到一个无向图,称之为,D,的基础图,记为,G(D).,对无向图链与路（圈与回路）这两个概念是一致的。,v1,v5,v4,v2,v3,e1,e8,e7,e6,e5,e4,e3,e2,有向图,路,链（点不同）,简单链（边不同）,第一节图论的基本概念（,13,）,对有向简单图,G,（,V,，,E,）对应着一个,|V|,|V,|,阶矩阵,A,（,a,ik,),，其中,则称矩阵,A,是,图,G,的邻接矩阵,例,设图为,则,其邻接矩阵为,返回,第二节图的连通与割集（,1,）,在图,G,中的，一个点和边的交替序列,（,n,i,，,e,ij,，,n,j,，,n,k,，,e,kl,，,n,l,）,称为,G,中由,n,i,到,n,l,的一条路，记为,n,i,n,l,简单路：,如果路中的边不重复，称为简单路,当,G,是简单图时，,一、图的连通,初级路：,如果路中的点不重复，称为初级路,由,n,i,到,n,l,的一条路可以用点的序列,来,表示：,（,n,i,，,n,j,，,n,k,，,n,l,）,回路：,在,G,中，一条至少包含一条边，并且,n,i,n,l,的,n,i,n,l,称为,G,点一条回路。,树：,一个无圈的连通图称为树。,性质：树,G=,（,V,，,E,）的顶点数为,p,，边数为,q,，则,q=p-1,。,例如：,支撑树：,图,T=,（,V,，,E,）,是图,G=,（,V,，,E,）的支撑子 图，若图,T,是一个树，则称,T,是图,G,的一个支撑树。,10.2,树,10.2.1,树与支撑树,定理,3,：,设图,G=(V,E),是一个树,顶点个数,则,G,中至少有两个悬挂点。,定理,4,：,设图,G=(V,E),是一个树的充分必要条件是,G,不含圈，且恰有 条边,。,定理,5,：,设图,G=(V,E),是一个树的充分必要条件是,G,是连通图，且边数,定理,6,：,设图,G=(V,E),是一个树的充分必要条件是,G,的任意顶点之间恰有一条链。,（,1,）,G,不含圈,（,2,）,G,是连通图,（,3,）,（,4,）图,G=(V,E),是一个树,上述条件有两个成立，就推出其余条件成立。,树的性质：,1,在图中任意两点之间必有一条而且只有一条通路。,2,在图中划去一条边，则图不连通。,树是边最少的连通图,3,在图中不相邻的两个顶点之间加一条边，可得一个且仅得一个圈。,4,图中边数有,n=p-1,（,p,为顶点数）,支撑树和最小支撑树的实际应用,在实际生活中，支撑树和最小支撑树有许多重要的应用。,例如：用网络,G,表示,n,个城市之间的通信线路，其中顶点表示城市，边表示两个城市之间的通信线路，边上的权值表示线路的长度或造价，由此构造了一个赋权图。我们可以通过求该图的最小支撑树达到求解通信线路或总代价最小的最佳方案。,求支撑树,“,破圈法”和“避圈法”,v,1,v,2,v,3,v,5,e,2,e,3,e,5,e,1,e,6,e,7,e,8,e,4,v,4,定理,7,：图,G,有支撑树，当且仅当图,G,是连通的。,v,1,v,2,v,5,e,2,e,3,e,5,e,1,e,6,e,7,e,8,e,4,v,4,我们给定一个连通图，如右所示，求它的支撑树。,破圈法,：在图中任选一个圈，从这个圈中去掉一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,v,3,v,1,v,2,v,5,e,2,e,3,e,5,e,1,e,6,e,7,e,8,e,4,v,4,v,1,v,2,e,1,v,3,e,2,e,4,v,4,v,5,e,6,避圈法,：开始选一条边，以后每一步中，总从未被选取的边中选出一条与已选边不构成圈的边。,v,3,根据破圈法和避圈法两种方式得到了图的两个不同的支撑树，由此可以看到连通图的支撑树不是唯一的。,v,1,v,2,v,3,v,5,e,1,e,6,e,8,e,4,v,4,10.2.2,最小支撑树问题,最小支撑树：,给图,G,中的每一条边（,v,i,，,v,j,）一个相应的数,ij,，则称,G,为赋权图。,ij,称为边（,v,i,v,j,）的权数。在赋权图,G,的所有支撑树中，必有某个支撑树，其所有边的权数和最小，称这个树为图,G,的最小支撑树。,求赋权图,G,的最小支撑树的方法也有两种，“破圈法”和“避圈法”。,破圈法,：在原图中，任选一个圈，从圈中去掉,权最大,的一条边。在余下的图中重复这个步骤，直到得到一不含圈的图为止。,6,5,5,1,7,2,3,4,4,v,1,v,2,v,3,v,4,v,5,v,6,v,3,v,2,1,v,4,2,v,5,3,v,6,4,v,1,5,6,5,5,1,7,2,3,4,4,v,1,v,2,v,3,v,4,v,5,v,6,避圈法,：开始选一条,权最小,的边，以后每一步中，总从未被选取的边中选一条权尽可能小，且与已选边不构成圈的边。,第三节最短路问题（,1,）,路的权,（或者路的长）：,给定一个有（无）向网络,G=(V,A,W),，设,P,为,G,中的一条有向路，令,则称,W(P),为,路径,P,的,权（,或,长）,最短路：,在网络,G,中，从顶点,u,到顶点,v,的,具有最小,权的路,P,(u,v),称为顶点,u,到顶点,v,的最短路。,在,无向网络图,中，最短路就简称为,最短路,在,有向网络图,中,，,最短路称为,最短有向路,最短路是一条路径，且最短路的任一段也是最短路,最短路有一个重要而明显的性质,：,第三节最短路问题（,6,）,Dijkstra,算法中的符号：,P,：表示某个点的,P,标号（永久标号）,T,：,表示某个点的,T,标号（临时标号）,S,i,：表示第,i,步时具有,P,标号点的集合,(v),m,：表示从,V,s,到,V,的最短路上，,V,的前一,个点是,V,m,(v),M,：表示,G,中不含从,V,s,到,V,的路,(v),0,：表示,V,V,s,Dijkstra,算法的具体步骤：,第三节最短路问题（,7,）,Dijkstra,算法步骤：,第,0,步,：,(,开始,i=0,）令,S,0,=V,s,，,(V,s,),0,对每一个,V,V,s,令,T,（,V,）,，,(V),M,令,K,s,第,1,步,：若,S,i,=V,，则算法终止，这时每个,V,都在,S,i,中，,最短路长为,P(V),第,2,步,：考察每个,(V,k,V,j,)E,且,V,j,S,i,的点,V,j,如果,T(V,j,)P(V,k,)+w,kj,则把,T(V,j,),修改为,P(V,k,)+w,kj,，,把,(V,j,),修改为,k,否则,转,第,3,步,第,3,步,：令,若,T(V,ji,),则,V,ji,的,T,标号变为,P,标号，,P(V,ji,)=,T(V,ji,),令,S,i+1,=S,i,V,ji,k=ji,把,i,换成,i+1,转,第,1,步，否则终止,第三节最短路问题（,8,）,例 求,V,1,到其余各点的最短距离,V,1,V,2,V,5,V,4,V,3,V,6,V,7,V,8,V,9,1,6,3,2,2,10,6,4,1,10,2,2,4,3,3,6,第三节最短路问题（,9,）,例,求下图下列有向图的顶点,u,1,到其余顶点的最短有向路,解,：,第一步,置,i=0,，,S,0,=V,1,P(V,1,)=0,(V1)=0,令,T,（,V,i,）,，,(V,i,),M,(i=2,3,6),k=1,V,6,V,1,V,2,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,V,6,V,1,V,2,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,4,第三节最短路问题（,10,）,V,6,V,1,V,2,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,4,3,10,8,把,T(V,2,),修改为,P(V,1,)+W,12,=5,(V,2,)=1,同理,T(V,4,),3,T(V,6,),4,(V,4,),1,在所有,T,标号中,T(V,4,)=3,最小，令,P(V,4,)=3,S,1,=V,1,V,4,k=4,第三节最短路问题（,11,）,V,6,V,1,V,2,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,4,3,10,8,4,i=1,，把,T(V,5,)=8,T(V,3,)=10,(V,5,),4,(V3)=4,在所有,T,标号中,T(V,6,)=4,最小，令,P(V,6,)=4,S,2,=V,1,V,4,V,6,k=6,第二步,第三节最短路问题（,12,）,V,2,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,10,8,4,置,P=1,4,6,，,T=2,3,5,置,P=1,2,4,6,，,T=3,5,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,8,8,4,V,2,第三节最短路问题（,13,）,置,P=1,2,4,6,，,T=3,5,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,8,8,4,V,2,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,8,8,4,V,2,置,P=1,2,3,4,6,，,T=5,第三节最短路问题（,14,）,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,8,8,4,V,2,置,P=1,2,3,4,6,，,T=5,V,6,V,1,V,4,2,6,4,5,3,2,3,5,V,3,V,5,7,4,1,0,5,3,8,8,4,V,2,置,P=1,2,3,4,5.6,，,T=,第三节最短路问题（,15,）,例,2,求下图从顶点,V,1,到其余顶点的最短路,解,：,第一步,置,u,1,=0,，,u,j,=w,1j,，,j=2,3,8,，,P=1,，,T=2,3,8,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,0,2,8,1,第,2,步,在,T,中寻找一点,k,，使得,第三节最短路问题（,16,）,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,0,2,8,1,第,2,步,在,T,中寻找一点,k,，使得,得,k=3,置,P=1,3,，,T=2,4,5,6,7,8,1,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,0,2,8,10,第三节最短路问题（,17,）,1,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,0,2,3,8,10,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,8,6,10,12,第三节最短路问题（,18,）,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,10,12,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,8,6,10,12,第三节最短路问题（,19,）,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,10,12,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,9,12,第三节最短路问题（,20,）,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,9,12,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,9,12,第三节最短路问题（,21,）,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,9,12,V,8,V,1,V,2,V,3,9,3,8,2,1,6,1,9,V,5,V,7,2,4,3,V,4,V,6,7,5,1,6,1,0,2,3,7,6,9,12,最短路的应用（,1,）,一、可化为最短路问题的多阶段决策问题,例,1,设备更新问题：企业使用一台设备，每年年初，企业领导就要确定是购置新的，还是继续使用旧的,.,若购置新设备，就要支付一定的购置费用；若继续使用，则需支付一定的维修费用,.,现要制定一个五年之内的设备更新计划，使得五年内总的支付费用最少,.,已知该种设备在每年年初的价格为,：,第一年第二年第三年第四年第五年,11,11,12,12,13,使用不同时间设备所需维修费为：,使用年限,0,1,1,2,2,3,3,4,4,5,维修费,5,6,8,11,18,最短路的应用（,1-1,）,V,1,V,2,V,5,V,4,V,3,V,6,30,16,16,22,17,41,59,22,17,41,18,30,23,31,23,解：,把这个问题化为最短路问题。,设,b,i,表示设备在第,i,年年初的购买费,c,i,表示设备使用,i,年后的维修费,V,=,v,1,v,2,v,6,点,v,i,表示第,i,年年初购进一台新设备,虚设一个点,v,6,表示第,5,年年底,.,E,=,v,i,v,j,|1,i,j,6,.,这样上述设备更新问题就变为：在有向赋权图,G,=(,V,E,F,)(,图解如下,),中求,v,1,到,v,6,的最短路问题,.,最短路的应用（,5,）,也可构造加权有向图,G2(V,E),（,1,）顶点集,V=,，,表第,i,年初购置新设备的,决策，表第五年底,.,(2),弧集,E=(V,i,V,j,),i=1,2,3,4,5;ij6,弧,(V,i,V,j,),表第,i,年初购进一台设备一直,使用到第,j,年初的决策，其权,W(V,i,V,j,),表由这一决策在第,i,年初到第,j,年初的总,费用，如,W(V,1,V,4,)=11+5+6+8=30.,(3),问题转化为求,V,1,到,V,6,的最短路问题，,求得两条最短路为,，,权为,53,，与图,G1(V,E),的解相同,由实际问题可知,设备使用三年后应当更新,因此删除该图中,v,1,到,v,5,v,1,到,v,6,v,2,到,v,6,的连线；又设备使用一年后就更新则不划算,因此再删除该图中,v,1,v,2,v,2,v,3,v,3,v,4,v,4,v,5,v,5,v,6,五条连线后得到,从上图中容易得到,v,1,到,v,6,只有两条路：,v,1,v,3,v,6,（费用,22+31,）,和,v,1,v,4,v,6,（费用,22+31,）,.,而这两条路都是,v,1,到,v,6,的最短路,.,-,0,(v,1,),(v,1,),(v,1,),(v,1,1),v,1,1,(v,1,6),(v,1,6),(v,1,3),(v,1,),(v,1,),(v,4,11),(v,1,),(v,1,),(v,1,),(v,1,3),v,1,3,(v,1,),(v,1,),(v,1,),(v,1,),(v,3,5),v,3,5,(v,4,11),(v,4,11),(v,1,),(v,1,),(v,2,6),v,2,6,(v,1,),(v,5,9),v,5,9,(v,5,10),(v,5,12),(v,1,),(v,5,10),v,5,10,(v,5,12),(v,1,),(v,1,),(v,5,12),v,5,12,(v,1,),(v,1,),v,1,对无向图，用类似方法可求,例：利用,Dijkstra,标号法求右图中,v,1,到,v,8,的最短路。,v,1,v,2,v,3,v,4,v,5,v,6,v,7,v,8,v,9,6,1,2,2,3,1,10,6,4,10,2,4,3,2,6,3,v,i,(v,j,a),v,j,a,(v,1,),v,1,v,8,v,5,v,2,v,3,v,1,给一个有向图,D(V,A)，,指定两个点，一个称为,发,点,，记为,v,s,，,另一个点称,为,收点,，记为,v,t,，,其余点,称为中间点。,对于,D,中的每一个弧(,v,i,v,j,)，,相应,地给,一个数,c,ij,（c,ij,0），,称为弧(,v,i,v,j,),的容量。我们把这样的,D,称为网络（或容量网络），记为,D(V,A,C)。,如上图。,10.4,最大流问题,10.4.1,基本概念和定理,3,5,1,1,4,2,3,5,2,v,s,v,2,v,1,v,3,v,4,v,t,所谓网络上的,流,，是指定义在弧集,A,上的函数,ff(v,i,v,j,)，,并称,f(v,i,v,j,),为弧(,v,i,v,j,),上的,流量,，简记为,f,ij,。,3,1,5,2,1,0,1,0,4,1,2,2,3,1,5,2,2,1,v,s,v,2,v,1,v,3,v,4,v,t,容量：每个弧上的最大通过能力，用,c,ij,表示，即弧上的第一个数字；,流量：弧上实际通过的流量，用,x,ij,表示，弧上的第二个数字；显然,0=x,ij,=c,ij,，如果,x,ij,=c,ij,则称为饱和弧；,截集：,分离始点,vs,和终点,vt,的弧的集合，叫做,截集,截量：,截集的容量叫做,截量,可行流：,（,1,）,（,2,）各点流入量,=,流出量，且,vs,的流出量,=vt,的流入量，这样的流称之为,可行流,的弧称为,饱和弧,；,的弧称为,非饱和弧。,的弧称为,零流弧,；的弧称为,非零流弧,。,若,是网络中从发点到收点的链，链上的弧分为两类：,一类与链的方向一致，叫做,前向弧，,记为,；另一类与链的方向相反，叫做,后向弧，,记为,。,增广链：,是可行流，,是一条从发点到收点的链，,若在前向弧上，即在 中每一弧是非饱和弧；,在后向弧上，即在 中每一弧是非零流，则称此链为,增广链。,v,s,v,t,v,2,v,1,v,4,v,3,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(2,1),(5,3),增广链,：是可行流，,是一条从发点到收点的链，,若在前向弧上，即在 中每一弧是非饱和弧；,在后向弧上 ，即在 中每一弧是非零流，则称此链为,增广链。,13(5),9(3),4(1),5(3),6(3),5(2),5(2),5(0),4(2),4(1),9(5),10(1),是一个增广链,显然图中增广链不止一条,4、容量网络,G=（V，E，C），,v,s,为始点，,v,t,为终点。如果把,V,分成两个非空集合,使 ，则所有始点属于,S，,而终点属于 的弧的集合，称为由,S,决定的截集,记作 。截集 中所有弧的容量之和，称为这个截集的容量，记为 。,v,s,v,1,v,2,v,4,v,3,v,t,3,7,4,5,5,6,3,7,8,S,13(5),9(3),4(1),5(3),6(3),5(2),5(2),5(0),4(2),4(1),9(5),10(1),设 ，,则截集为,容量为24,求下图所示网络中的最大流，弧旁数为,(1,1),v,2,v,1,v,4,v,3,v,s,v,t,(3,3),(5,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),(1,1),v,2,v,1,v,4,v,3,v,s,v,t,(3,3),(5,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),（0，+）,（-,v,1,1）,（+,v,s,4）,（-,v,2,，1）,（+,v,2,，1）,(+,v,3,，1),(1,0),v,2,v,1,v,4,v,3,v,s,v,t,(3,3),(5,2),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),(1,0),v,2,v,1,v,4,v,3,v,s,v,t,(3,3),(5,2),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),（0，+）,（+,v,s,3）,最小截集,13(5),9(3),4(1),5(3),6(3),5(2),5(2),5(0),4(2),4(1),9(5),10(1),13(11),9(9),4(0),5(5),6(6),5(5),5(4),5(4),4(4),4(3),9(9),10(7),截集1,截集2,最小截量为：,9+6+5=20,70（70）,70（50）,130（100）,150（130）,150（150）,50（20）,50（50）,120（30）,100（100）,（120）,（230）,（150）,（200）,1,标号,方法很简单：首先找到一条增广链，沿此进行最大可能调整，再找增广链，再调整，直到没有增广链。,寻找增广链的标号法：先给,v,s,标号（,0,，,+,）,而后依次审查各条弧（,v,i,v,j,）：,对前向弧,，饱和否？不饱和（使其增加），给,v,j,点标号（,v,i,，,l(v,j,);,对后向弧，是否非零流弧（使其减少）？是，给,v,j,标号（,-vi,l(v,j,),）,直到给,v,t,标上号，就得到了增广链。,调整,对于增广链,，,求最大流的方法,调整,令：,得到新的可行流，重新标号，直至标不下去为止。,例：解水网最大流问题,v,s,V,2,(0,+,),V,1,(3,3),(5,1),(1,1),(4,3),(1,1),(2,2),(3,0),(5,3),(2,1),V,4,V,3,V,t,(v,s,4),(-v,1,1),(-v,2,1),(v,2,1),(v,3,1),1,标号,对前向弧,，饱和否？不饱和（使其增加），给,vj,点标号（,vi,，,l(vj);,对后向弧,，是否非零流弧（使其减少）？是，给,vj,标号（,-vi,l(vj),）,直到给,vt,标上号，就得到了增广链。,v,s,V,2,(0,+,),V,1,(3,3),(5,2,),(1,0,),(4,3),(1,0,),(2,2),(3,0),(5,3),(2,2,),V,4,V,3,V,t,(v,s,3),2,沿增广链进行调整，,前向弧增加,1,，后向弧减少,l,。,v,s,V,2,(0,+,),V,1,(3,3),(5,2),(1,0),(4,3),(1,0),(2,2),(3,0),(5,3),(2,2),V,4,V,3,V,t,(v,s,3),v,s,V,2,V,1,V,3,V,4,V,t,(3,3),(5,2),(4,3),(1,0),(1,0),(2,2),(3,0),(5,3),(2,2),(0,+),(vs,3),重新标号，直至标不下去为止。最小截集为,（,v,s,，,v,2,），（,v,1,，,v,3,),容量为,5,。最大流也为,5,。,例,1,：求从发点,V1,到收点,V7,的最大流。弧的流量放在括号内。如图,.,V=20,v,1,v,2,v,3,4,v,5,v6,v,7,8(6),6(6),3(3),14(10),3(0),8(7),3(1),4(1),10(3),7(7),6(6),4(3),关于最大流问题的定理：,定理1,可行流,f,*,f,ij,*,是最大流，当且仅当,D,中不存在关于,f,*,的增广链。,定理2,（最大流最小截定理）,任一网络中，最大流的流量等于最小截集的截量。,10.4.2,求最大流的标号法,标号法思想,：,先找一个可行流。,对于,这,个可行流,，,经过标号过程，得到从发点,v,s,到收点,v,t,的增广链；,经过调整过程,，,沿增广链增加可行流的流量,，,得到新的可行流,。重复这一过程，直到可行流无增广链，得到最大流。,标号法,步骤,：,(1),给,v,s,标号(,0,+,)，,v,s,成为已标号未检查的点，其余都是未标号点。,(2),取一个已标号未检查的点,v,i,，,对一切未标号点,v,j,：,若有非饱和弧(,v,i,v,j,)，,则,v,j,标(,v,i,l(v,j,)，,其中,l(v,j,)minl(v,i,),c,ij,-f,ij,，v,j,成为已标号未检查的点；若有非零弧(,v,j,v,i,)，,则,v,j,标号(-,v,i,l(v,j,)，,其中,l(v,j,)minl(v,i,),f,ji,，v,j,成为已标号未检查的点。,v,i,成为已标号已检查的点。,(3),重复步骤(2)，直到,v,t,成为标号点或所有标号点都检查过。若,v,t,成为标号点，表明得到一条,v,s,到,v,t,的增广链，转入调整过程；若所有标号点都检查过，表明这时的可行流就是最大流，算法结束。,调整过程：在增广链上，前向弧流量增加,l(v,t,)，,后向弧流量减少,l(v,t,)。,下面用实例说明具体的操作方法：,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),v,s,v,2,v,1,v,3,v,4,v,t,(3,3),(5,1),(1,1),(1,1),(4,3),(2,2),(3,0),(5,3),(2,1),v,s,v,2,v,1,v,3,v,4,v,t,在左图给出的可行流的基础上，求,v,s,到,v,t,的最大流。,(-,+),(v,s,4),(-v,1,1),(-v,2,1),(v,2,1),(v,3,1),(3,3),(5,2),(1,0),(1,0),(4,3),(2,2),(3,0),(5,3),(2,2),v,s,v,2,v,1,v,3,v,4,v,t,(v,s,3),(-,+),得增广链，标号结束，进入调整过程,无增广链，标号结束，得最大流。同时得最小截。,