《管理运筹学 图与网络分析.pptx》由会员分享，可在线阅读，更多相关《管理运筹学 图与网络分析.pptx（83页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、本章主要内容本章主要内容1 图的基本概念图的基本概念2 最小树问题最小树问题3 最短路问题最短路问题4 最大流问题最大流问题第1页/共83页1 1 图的基本概念图的基本概念具体问题的图具体问题的图第2页/共83页第3页/共83页第4页/共83页抽象问题的图抽象问题的图第5页/共83页蛋白质相互作用图第6页/共83页基因相互作用关系图第7页/共83页具体问题的图：具体问题的图：城市之间的铁路交通图、地铁线路图、城市之间的铁路交通图、地铁线路图、航空线路图等。航空线路图等。抽象问题的图：抽象问题的图：球队进行比赛的关系图、球队进行比赛的关系图、一群人的认识一群人的认识关系图、社交网络图、基因调控关
2、系图等关系图、社交网络图、基因调控关系图等 图是反映对象之间关系的一种工具，如果我们把对象图是反映对象之间关系的一种工具，如果我们把对象用点表示，关系用线表示，就构成了一个图。用点表示，关系用线表示，就构成了一个图。关系关系对称的关系：对称的关系：甲与乙有这种关系，则乙与甲甲与乙有这种关系，则乙与甲也有这种关系，如两点之间的距离等。也有这种关系，如两点之间的距离等。不对称的关系不对称的关系：甲与乙有这种关系，但乙与：甲与乙有这种关系，但乙与甲未必有这种关系：如两个人的认识关系，甲未必有这种关系：如两个人的认识关系，比赛结果、交通路线中的单行线等。比赛结果、交通路线中的单行线等。第8页/共83页
3、关系的表示关系的表示对称的关系用边表示：对称的关系用边表示：e=vi,vj或或e=vj,vi不对称的关系用带箭头的弧表示：不对称的关系用带箭头的弧表示：a=(vi,vj)图的分类：图的分类：无向图：无向图：G=(V,E)有向图：有向图：D=(V,A)一般用一般用p 和和 q 分别表示一个图中的顶点数和边数分别表示一个图中的顶点数和边数第9页/共83页一、无向图中的一些概念一、无向图中的一些概念边的边的端点端点 e1=v1,v2称称v1,v2 相邻，相邻，e是是v1及及v2 的的关联边关联边环环：两个端点相同的边；：两个端点相同的边；多重边多重边：两个端点之间多于一条的边；：两个端点之间多于一条
4、的边；简单图简单图：无环、无多重边的图；：无环、无多重边的图；多重图多重图：无环、但允许有多重边的图：无环、但允许有多重边的图点次：点次：以以v为端点的边的条数，称为为端点的边的条数，称为v的点次，的点次，记为记为dG(v)或或d(v).（在计算点次时，环算在计算点次时，环算2次）次）悬挂点悬挂点：次为：次为1的点；的点；悬挂边悬挂边：悬挂点的关联边；：悬挂点的关联边；孤立点孤立点：次为：次为0的点；的点；奇点：奇点：次为奇数的点；次为奇数的点；偶点：偶点：次为偶数的点。次为偶数的点。e5v4v1v3v2e4e2e1e6e7e3v6v5e8第10页/共83页定理定理1.图图G=(V,E)中，所
5、有点的次之和是边数的两倍中，所有点的次之和是边数的两倍.即即定理定理2.2.任一个图中，奇点的个数是偶数。任一个图中，奇点的个数是偶数。证明：设证明：设V1和和V2分别是分别是G中奇点和偶点的集合，由定理中奇点和偶点的集合，由定理1，有，有第11页/共83页链链：图：图G=(V,E)中一个点边交替的序列中一个点边交替的序列如果满足如果满足则称之为一条联结则称之为一条联结vi1和和vik的链。的链。简单图中的链可以简记为简单图中的链可以简记为链的链的起点、中间点、终点起点、中间点、终点圈：圈：起点和终点重合的链。起点和终点重合的链。简单链（圈）简单链（圈）：链（圈）中所含的边均不相同。：链（圈）
6、中所含的边均不相同。初等链（圈）初等链（圈）：链（圈）中所含的点均不相同。又称：链（圈）中所含的点均不相同。又称为路（回路）为路（回路）连通图连通图：任何两个顶点之间至少有一条链的图。：任何两个顶点之间至少有一条链的图。连通分支连通分支：不连通图的每一个连通部分图。：不连通图的每一个连通部分图。第12页/共83页子图、支撑子图子图、支撑子图：图：图G=(V,E),G=(V,E),若若V V，E E，则称则称G是是G的子图；的子图；V=V，E E，则称则称G是是G的支撑子图。的支撑子图。割集：割集：设设G=(V,E)，S V,T=VS,(S,T)=e|e=vivj,vi S,vi T 则称则称(
7、S,T)是是G的一个割集。的一个割集。完全图完全图：一个简单图中若任意两点之间均有边相连，：一个简单图中若任意两点之间均有边相连，则称之为完全图。则称之为完全图。偶图（二分图）偶图（二分图）：如果一个图的顶点能够分成两个不：如果一个图的顶点能够分成两个不相交的非空集合相交的非空集合V1，V2，使同一集合中任意两点之间，使同一集合中任意两点之间均不相邻，则称之为偶图（二分图）。均不相邻，则称之为偶图（二分图）。第13页/共83页二、有向图中的一些概念二、有向图中的一些概念给定有向图给定有向图D=(V,A).基础图基础图：从：从D中去掉所有弧上的箭头后得到的无向图称为中去掉所有弧上的箭头后得到的无
8、向图称为D的基础图，记为的基础图，记为G(D).弧的始点、终点弧的始点、终点：a=(u,v),u为始点，为始点，v为终点。为终点。链链：D中的一个点弧交替序列，如果在基础图中对应的是中的一个点弧交替序列，如果在基础图中对应的是一条链，则称之为一条链，则称之为D的一条链。（弧可以是逆向的）的一条链。（弧可以是逆向的）路路：如果一条链中的所有弧都是正向的，则称为一条路。：如果一条链中的所有弧都是正向的，则称为一条路。回路回路：起点和终点相同的路称为回路。：起点和终点相同的路称为回路。（简单路回路）、初等路（回路）可以类似定义。（简单路回路）、初等路（回路）可以类似定义。第14页/共83页引例引例:
9、自来水管道的铺设问题自来水管道的铺设问题校门校门A点点(水源水源);需要使用自来水的场所共有需要使用自来水的场所共有7个个:v1,v2,v7;问题问题:为了各个场所都用上自来水为了各个场所都用上自来水,怎样铺设管道才怎样铺设管道才能使挖开的道路数目最少能使挖开的道路数目最少?Av1v2v3v4v7v6v52374355245627第15页/共83页Av1v2v3v4v7v6v5Av1v2v3v4v7v6v5共挖开共挖开9条路条路共挖开共挖开6条路条路第16页/共83页2 最小树问题最小树问题1.树的定义及性质树的定义及性质2.图的支撑树图的支撑树3.最小树问题最小树问题第17页/共83页1.树
10、的定义及性质树的定义及性质定义定义:无圈的连通图称为树无圈的连通图称为树.e1e2e4e3v4v1v5v3v2v6v7v8e5e6e7第18页/共83页树的性质树的性质：1.设设G是一个树，是一个树，p(G)2,则则G中至少有中至少有两个悬挂点。两个悬挂点。2.如下三个论断中的两个保证如下三个论断中的两个保证G是树：是树：（1）连通）连通;（2）无圈）无圈;（3）q(G)=p(G)-1.3.G=(V,E)是一个树的充要条件是是一个树的充要条件是G中任意两个顶点间有且仅中任意两个顶点间有且仅有一条链。有一条链。4.从一个树中去掉任意一条边，则余下的图是不连通的。从一个树中去掉任意一条边，则余下的
11、图是不连通的。5.在树中不相邻的两个点间添上一条边，恰好得到一个圈。在树中不相邻的两个点间添上一条边，恰好得到一个圈。e1e2e4e3v4v1v5v3v2v6v7v8e5e6e7第19页/共83页2.图的支撑树图的支撑树定义定义：设：设T=(V,E）是图是图G=(V,E)的支撑子图，如的支撑子图，如果果T=(V,E)是一个树，则称是一个树，则称T是一个支撑树。是一个支撑树。v1v5v4v3v2e1e2e3e6e7e8e5e4v1v5v4v3v2e1e3e6e8图图 GG的一个支撑树的一个支撑树第20页/共83页连通图的支撑树满足连通图的支撑树满足：（1 1）支撑性；（）支撑性；（2 2）连通性
12、；（）连通性；（3 3）无圈性。）无圈性。2.求连通图的支撑树的方法：求连通图的支撑树的方法：支撑性支撑性连通性连通性无圈性无圈性破圈法破圈法支撑性支撑性无圈性无圈性连通性连通性避圈法避圈法连通性连通性无圈性无圈性支撑性支撑性反圈法反圈法第21页/共83页破圈法破圈法找圈、破圈、直到无圈为止找圈、破圈、直到无圈为止Av1v2v3v4v7v6v5第22页/共83页避圈法避圈法（1 1）由连通图的所有顶点生成一个不含边的子图；）由连通图的所有顶点生成一个不含边的子图；（2 2）加边，但不能生成圈，直到连通为止。）加边，但不能生成圈，直到连通为止。Av1v2v3v4v7v6v5第23页/共83页反圈
13、法反圈法把图的顶点分成把图的顶点分成S和和VS两部分，则割集两部分，则割集(S,VS)中必有一中必有一条边包含在图的支撑树中。条边包含在图的支撑树中。SVS第24页/共83页Av1v2v3v4v7v6v5第25页/共83页Av1v2v3v4v7v6v52374355245627思考：假若考虑道路的长度，要求挖开的路面总长度思考：假若考虑道路的长度，要求挖开的路面总长度最短，问题该如何解决？最短，问题该如何解决？这就是我们接下来要介绍的这就是我们接下来要介绍的最小树最小树问题问题第26页/共83页3.最小树问题最小树问题赋权图赋权图:给图给图G=V,E中的每一条边中的每一条边vi,vj赋上一个数
14、字赋上一个数字wij,称这样的图为赋权图，称这样的图为赋权图，wij称为边称为边vi,vj上的权。上的权。权可以表示距离、时间、费用等，通常为非负值。权可以表示距离、时间、费用等，通常为非负值。Av1v2v3v4v7v6v52374355245627第27页/共83页支撑树的权支撑树的权：如果：如果T=(V,E)是是G的一个支撑树，则称的一个支撑树，则称E 中所有边的权之和为支撑树中所有边的权之和为支撑树T的权，记为的权，记为w(T)。即即Av1v2v3v4v7v6v52374355245627上例中支撑树的权为上例中支撑树的权为 3+7+5+2+2+3+4=26第28页/共83页最小支撑树最
15、小支撑树：如果支撑树：如果支撑树T*的权的权w(T*)是是G的所有的所有支撑树的权中最小者，则称支撑树的权中最小者，则称T*是是G的最小支撑树的最小支撑树（简称最小树）。（简称最小树）。最小树问题最小树问题：求一个赋权图的最小支撑树。：求一个赋权图的最小支撑树。第29页/共83页求最小树的方法求最小树的方法1.破圈法破圈法2.避圈法（避圈法（Kruskal算法）算法）3.反圈法反圈法(Dijkstra算法算法)第30页/共83页破圈法破圈法从赋权图中任取一个圈，去掉圈中权最大的边，直从赋权图中任取一个圈，去掉圈中权最大的边，直到无圈为止。到无圈为止。Av1v2v3v4v7v6v52374355
16、245627第31页/共83页避圈法避圈法Step 1 将赋权图将赋权图G中的所有边按权从小到大排序；中的所有边按权从小到大排序；Step 2 取取G的所有顶点生成一个不含边的图的所有顶点生成一个不含边的图T；Step 3 将将G的边按权从小到大的顺序依次添加到的边按权从小到大的顺序依次添加到T中，中，使使T中不含圈，直到中不含圈，直到T成为连通图为止。（对于形成成为连通图为止。（对于形成圈的边不添加）圈的边不添加）Av1v2v3v4v7v6v52374355245627第32页/共83页反圈法反圈法定理：把图的顶点分成定理：把图的顶点分成S和和 VS两部分，则割集两部分，则割集(S,VS)中
17、权中权最小的边必包含在图的最小支撑树中。最小的边必包含在图的最小支撑树中。75210SVS第33页/共83页Step 1 从图从图G中任取一点中任取一点vi,让让vi S,其余各点均包含在其余各点均包含在S=VS中。中。Step 2 从（从（S,S)中选一条权最小的边中选一条权最小的边e=vivj，加到加到T中。中。Step 3 令令S vjS,S vjS，(将所选边的另一个顶点将所选边的另一个顶点添加到添加到S中）。中）。Step 4 重复重复2、3两步，直到图中所有点均包含在两步，直到图中所有点均包含在S中为止。中为止。第34页/共83页Av1v2v3v4v7v6v523743552456
18、27第35页/共83页课堂练习：课堂练习：1.1.分别用三种方法求下图的最小支撑树分别用三种方法求下图的最小支撑树254317434157v1v2v3v4v5v6v7第36页/共83页水源水源2.2.某农场的水稻田用堤埂分割成很多小块。为了某农场的水稻田用堤埂分割成很多小块。为了用水灌溉，需要挖开一些堤埂。问最少挖开多少条用水灌溉，需要挖开一些堤埂。问最少挖开多少条堤埂，才能使水浇灌到每小块稻田？堤埂，才能使水浇灌到每小块稻田？第37页/共83页作业作业P221P221：第第3 3题题第38页/共83页3 3 最短路问题最短路问题1.问题的提出问题的提出2.最短路问题的最短路问题的Dijkst
19、ra算法算法3.求任意两点之间最短距离的矩阵算法求任意两点之间最短距离的矩阵算法第39页/共83页1.问题的提出问题的提出例例1.已知如图所示交通网络图，边旁的数字表示通过已知如图所示交通网络图，边旁的数字表示通过这段路所需要的费用，现某人要从这段路所需要的费用，现某人要从v1出发到出发到v8去，问去，问他该走哪条路线才能花费最少？他该走哪条路线才能花费最少？该问题就是要在赋权图中所有从该问题就是要在赋权图中所有从v1到到v8 的路中，找一条的路中，找一条权最小的路。称之为权最小的路。称之为最短路最短路。其中路的权指路上所有边对应的权之和，又称为其中路的权指路上所有边对应的权之和，又称为路长路
20、长。v1v6v4v7v2v5v8v3786788764253第40页/共83页2.最最短路问题的短路问题的Dijkstra算法算法当边当边(弧弧)权权wij 0 时，目前公认的求最短路的最好算法时，目前公认的求最短路的最好算法是由是由Dijkstra于于1959年提出的，称为年提出的，称为Dijkstra算法算法。这个。这个算法事实上可以求出从一个给定的点到任意点的最短路。算法事实上可以求出从一个给定的点到任意点的最短路。算法的基本原理：算法的基本原理：v1v2v3348v1v2v31028问：问：1.上图中从上图中从v1 到到v3 的最短路分别是多少？的最短路分别是多少？2.两图中从两图中从
21、v1 到到v3 的边权相等，为什么最短路不同？的边权相等，为什么最短路不同？第41页/共83页3.假若假若v2 到到v3 的边权不知道的边权不知道(如下图如下图)，还能否确定从，还能否确定从v1到到v3的最短路？的最短路？v1v2v33?8v1v2v310?8左图无法确定左图无法确定,右图中最短路为从右图中最短路为从v1直接到直接到v3,路长为路长为8.第42页/共83页例例：某某人人要要从从甲甲地地到到乙乙地地，可可以以选选择择的的路路线线共共有有4条条，分分别别需需要要经经过过A、B、C、D四四个个地地方方，如如下下图图。假假如如经经过过A、B去去乙乙地地的的路路长长已已知知；而而从从甲甲
22、地地经经过过C、D到到乙乙地地的的路路长长未未知知，但但是是从从甲甲到到C、D的的路路长长已已知知，分分别别为为20、45公公里里，那那么么能能否否确确定定从从甲甲地地经经过过A、B、C、D哪哪个个地地方去乙地最近？方去乙地最近？甲乙乙ABCD5公里公里7公里公里15公里公里9公里公里20公里公里？公里？公里45公里公里？公里？公里很很明明显显，选选择择经经过过A到到乙乙地地一一定定是是最最短短的的路路。因因为为从从C、D到到乙乙地地的的路路长长虽虽然然还还不不知知道道，但但是是根根据据已已知知条条件件，可可以以推推断断出出它它们们的的路路长长一一定定比比12公公里里长长，所所以以不不会会比比
23、经过经过A到乙地短。到乙地短。第43页/共83页算法的实现过程算法的实现过程：从起点出发，逐步向外探寻最短路，直到终点。从起点出发，逐步向外探寻最短路，直到终点。探寻最短路的方式：探寻最短路的方式：给顶点标号给顶点标号（标出从起点到各顶点的最短路及路长）（标出从起点到各顶点的最短路及路长）一一旦旦找找到到从从起起点点到到vi的的最最短短路路，我我们们就就给给顶顶点点vi标标上上标标号，其中号，其中 （a）起点起点vs的标号为的标号为0，0；（b）顶点顶点vi的标号为的标号为Lsi，i，其中其中Lsi 表示从表示从vs到到vi的最短路的路长，的最短路的路长，i用来说明顶点用来说明顶点vi的标号是
24、从哪个的标号是从哪个顶点得到的（最短路的来源）。顶点得到的（最短路的来源）。第44页/共83页算法的步骤：算法的步骤：1.给始点给始点vs（最短路的起点）标号（最短路的起点）标号0，0。2.确定割并计算相应的指标值：确定割并计算相应的指标值：由由所所有有一一个个端端点点已已标标号号另另一一个个端端点点未未标标号号的的边边构构成成割割，记为：记为：对割里的每一条边对割里的每一条边（vi，vj），按下式计算指标按下式计算指标kij值：值：kij=Lsi+wij即即kij等等于于边边（vi，vj）中中的的已已标标号号点点vi的的标标号号（Lsi，i）中的中的Lsi加上边加上边（vi，vj）的权的权w
25、ij。第45页/共83页3 扩大标号范围。扩大标号范围。找出当前割中指标值最小的一条边，给该边的未标找出当前割中指标值最小的一条边，给该边的未标号点号点vj标号标号（kij,vi）。4.重复重复2、3两步，直到终点两步，直到终点vt得到标号为止。得到标号为止。第46页/共83页第51页/共83页v1v6v4v7v2v5v8v3786788764250，06，v17，v138，v112，v414，v414，v519，v7最短路为：最短路为：v1 v4 v5 v7 v8 路长为路长为19例求例例求例1中中v1到到v8的最短路的最短路第55页/共83页例例3：求下图中：求下图中v1到到v8的最短路。
26、的最短路。V1V2V3V4V5V6V7V8V966623121104324230,01,V13,V13,V45,V36,V28,V59,V510,V511,V9最短路长为最短路长为11。(1)v1v4v3v2v5v9v8(2)v1v3v2v5v9v8第56页/共83页.求任意两点之间最短距离的矩阵算法求任意两点之间最短距离的矩阵算法Dijkstra算法提供了求图中从给定点到任一其它点的最短算法提供了求图中从给定点到任一其它点的最短路的方法。路的方法。若需要计算图中任意两点之间的最短距离。如何计算？若需要计算图中任意两点之间的最短距离。如何计算？定义图中任意两点之间的邻接距离矩阵定义图中任意两点
27、之间的邻接距离矩阵D(0)构造任意两点之间最多经过一个中间点即可到达的最构造任意两点之间最多经过一个中间点即可到达的最短距离矩阵短距离矩阵D(1)再构造再构造D(2),表示最多经过个中间点即可到达的最短表示最多经过个中间点即可到达的最短距离矩阵距离矩阵直到直到D(k)=D(k-1)第57页/共83页v1v5v2v33655224v4第58页/共83页课堂练习课堂练习:求下图中求下图中v1到其它各点的最短路及路长到其它各点的最短路及路长82567722962352v1v2v3v4v5v6v7v8作业：作业：P221P221：第第4 4题题第59页/共83页4 4 最大流问题最大流问题1.问题的提
28、出问题的提出2.基本概念与基本定理基本概念与基本定理3.寻求最大流的标号法（寻求最大流的标号法（Ford Fulkerson）第60页/共83页1.问题的提出问题的提出下图为联结某产品的产地下图为联结某产品的产地v1和销地和销地v6的交通网，每一条的交通网，每一条弧弧(vi,vj)代表从代表从vi到到vj的运输线，弧旁的数字表示运输线的运输线，弧旁的数字表示运输线的最大通过能力，产品经过交通网从的最大通过能力，产品经过交通网从v1运到运到v6,要求制定要求制定一个运输方案，使从一个运输方案，使从v1运到运到v6的产品数量最多。的产品数量最多。v1v2v3v4v5v6108453563119第6
29、1页/共83页2.基本概念与基本定理基本概念与基本定理1.网络与流网络与流网络网络：D=(V,A,C),满足下列条件：满足下列条件：（1）有向图；）有向图；（2）有一个发点）有一个发点(vs)、一个收点、一个收点(vt)和若干中间点；和若干中间点；（3）每一条弧）每一条弧(vi,vj)A都对应一个容量都对应一个容量c(vi,vj)0.网络上的流网络上的流：定义在弧集合上：定义在弧集合上的一个函数的一个函数f=f(vi,vj)(fij).称称 f(vi,vj)为弧为弧(vi,vj)上的流量。上的流量。vsv2v3v4v5vt1084535631195064155056第62页/共83页2.可行流
30、与最大流可行流与最大流可行流可行流：满足以下条件的流：满足以下条件的流 1)容量限制容量限制：对任意对任意(vi,vj)A，0 fij cij。2)平衡条件：平衡条件：中间点：流入量中间点：流入量=流出量流出量 发点：流出量发点：流出量-流入量流入量=流量流量v(f)收点：流入量收点：流入量-流出量流出量=流量流量v(f)最大流问题最大流问题：求一个可行流求一个可行流fij，使使v(f)达到最大。达到最大。第63页/共83页3.3.增广链增广链给定一个可行流，网络中的弧可以分为：给定一个可行流，网络中的弧可以分为：饱和弧饱和弧非饱和弧非饱和弧零流弧零流弧非零流弧非零流弧给定一条从发点给定一条从
31、发点vs到收点到收点vt的链的链，定义链的方向是，定义链的方向是从从vs到到vt，则链上的弧被分成两类：则链上的弧被分成两类：（1）前向弧前向弧 +（2）后向弧后向弧 -增广链增广链：从发点：从发点vs到收点到收点vt的链的链，若满足：每一条前向，若满足：每一条前向弧都是非饱和弧，每一条后向弧都是非零流弧，则称之弧都是非饱和弧，每一条后向弧都是非零流弧，则称之为增广链。为增广链。vsv2v3v4v5vt1084535631195064155056第64页/共83页4.4.割集与割的容量割集与割的容量割集的容量：割集的容量：任何一个可行流的流量都不会超过任何一个割集的容量任何一个可行流的流量都不
32、会超过任何一个割集的容量定理定理2：可行流：可行流 f*是最大流的充要条件是是最大流的充要条件是D中不存在中不存在关于关于f*的增广链。的增广链。第65页/共83页3.寻求最大流的标号法（寻求最大流的标号法（Ford Fulkerson）算法的思想：算法的思想：从一个可行流开始，寻找增广链。若找从一个可行流开始，寻找增广链。若找到就调整可行流；若找不到增广链，则当前的可行流到就调整可行流；若找不到增广链，则当前的可行流就是最大流。就是最大流。算法的实现：算法的实现：（1）标号过程）标号过程（2）调整过程）调整过程该算法是由该算法是由Ford和和Fulkerson于于1956年提出的，又年提出的
33、，又称称Ford-Fulkerson算法。算法。第66页/共83页（1 1）标号过程：）标号过程：检查的过程就是给邻点标号的过程。检查的过程就是给邻点标号的过程。已标号点已标号点未标号点未标号点已检查（所有邻点中该标的都标了）已检查（所有邻点中该标的都标了）未检查（邻点中还有该标号而未标的点）未检查（邻点中还有该标号而未标的点）当所有当所有vi的邻点都检查之后，的邻点都检查之后，vi成为标号已检查的点，成为标号已检查的点，而新得到标号的点成为标号未检查的点。而新得到标号的点成为标号未检查的点。第67页/共83页重复上述过程，直到重复上述过程，直到vt t得到标号或标号范围无法扩大为止。得到标号
34、或标号范围无法扩大为止。若若vt得到标号，则可找到一条增广链，否则算法结束。得到标号，则可找到一条增广链，否则算法结束。（2 2）调整过程）调整过程倒向追踪找到一条增广链倒向追踪找到一条增广链，令调整量，令调整量去掉标号，重复（去掉标号，重复（1 1）（）（2 2）两个过程。）两个过程。第68页/共83页例例1 1：用标号法求下列网络的最大流：用标号法求下列网络的最大流stv1v2v3v4（2，0）（5，3）（10,6）（6,6）（4,3）（2,1）（2，1）（7，1）（5，1）（5，5）0，stv1v2v3v4（2，0）（5，3）（10,6）（6,6）（4,3）（2,1）（2，1）（7，1）
35、（5，1）（5，5）s，2v1，2v3,2s，4v1，1解解第69页/共83页stv1v2v3v4（2，2）（5，5）（10,6）（6,6）（4,3）（2,1）（2，1）（7，1）（5，3）（5，5）0，s,4v2，1v2，1v3，1stv1v2v3v4（2，2）（5，5）（10,7）（6,6）（4,3）（2,0）（2，1）（7，1）(5，4)（5，5）0，s,3v2，1v4，1v4,1 v3，1第70页/共83页stv2v4（2，2）（5，5）（10,8）（6,6）（4,3）（2,0）（2，2）（7，0）（5，5）（5，5）0，s,2标号范围无法扩大，得到最大流，最小割。标号范围无法扩大，得
36、到最大流，最小割。v1v3第71页/共83页vsv2v1v3vt(2，2)(3，3)(5，2)(5，0)(2，1)(2，2)(8，1)例例2 2 （1 1）下图所给网络的流是否为可行流？）下图所给网络的流是否为可行流？（2 2）求出网络的最大流。）求出网络的最大流。第72页/共83页解解 （1 1）由于各条弧上的流量均为非负数且不超过容量，由于各条弧上的流量均为非负数且不超过容量，各中间点的流入量等于流出量，所以是可行流。各中间点的流入量等于流出量，所以是可行流。vsv2v1v3vt(2，2)(3，3)(5，2)(5，0)(2，1)(2，2)(8，1)0，vs，3v1，3v2，1v3，1第73
37、页/共83页vsv2v1v3vt(2，2)(3，3)(5，3)(5，1)(2，0)(2，2)(8，2)0，vs，2v1，2标号范围无法扩大，得到最大流，最小割。标号范围无法扩大，得到最大流，最小割。最大流的流量为：最大流的流量为：5第74页/共83页用用WINQSB求解图与网络问题求解图与网络问题最小树问题最小树问题最短路问题最短路问题最大流问题最大流问题第75页/共83页第76页/共83页第77页/共83页第78页/共83页第79页/共83页第80页/共83页课堂练习：课堂练习：1.求下图所示网络中从求下图所示网络中从vs到到vt的最大流，图中各弧旁的数字的最大流，图中各弧旁的数字为弧的容量。为弧的容量。10833145478第81页/共83页vsv2v1v3vt(4，4)(3，3)(7，4)(6，2)(5，3)(2，2)(9，5)2、（、（1）下图所给网络的流是否为可行流？）下图所给网络的流是否为可行流？（2）求出网络的最大流。）求出网络的最大流。作业作业 P223P223，第第9 9题题第82页/共83页感谢您的观看。感谢您的观看。第83页/共83页