网络分析与网络计划的概念39929.docx

《网络分析与网络计划的概念39929.docx》由会员分享，可在线阅读，更多相关《网络分析与网络计划的概念39929.docx（84页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第六章网络分析与网络计划网络分析是图论的一个应用分支它主要是应用图论的理论与方法来解决具有网络性质的管理决策问题在现实生活和生产实践中，网络分析方法有很广泛的应用如在企业管理中，如何制订管理计划或设备购置计划，使收益最大或费用最小；在组织生产中，如何使各工序衔接好，使生产任务完成得既快又好；在交通网络中，如何使调运的物资数量多且费用最小等由于网络分析具有图形直观，方法简便，容易掌握的特点，因此得到迅速的发展，且广泛地应用在各个领域，成为经济活动中许多管理决策的优化问题的重要手段网络计划方法是上世纪50年代发展起来的计划控制技术，主要包括计划评审技术(programme evaluation a

2、nd review technique，简称PERT)和关键路径方法(critical path method或critical path analysis，简称CPM、CPA)网络计划方法特别适用于现代管理中的多因素多环节的复杂计划的优化控制，成为管理运筹学的重要应用分支本章在引入入有关图图的一些些基本概概念的基基础上，介介绍最小小生成树树、网络络最短路路、最大大流、最最小费用用最大流流等网络络分析模模型及其其解法；并对网网络计划划图（统统筹图）的的制作、作作业时间间参数计计算、关关键线路路方法和和计划评评审技术术等网络络计划基基本技术术和方法法进行初初步介绍绍第一节 图图的基本本概念一、图

3、现实世界中中有许多多具体事事物及关关系可以以用图形形来抽象象表示例如，路路线关系系、工序序安排、区区位规划划等都可可以用图图来表达达我们先通过过几个直直观的例例子，来来认识什什么是图图例6-1 歌尼斯斯堡七桥桥问题哥尼斯堡(Konnigssberrgs)城域有有一个普普雷格尔尔河系，由由新河、旧旧河及其其交汇而而成的大大河组成成，它把把该城分分成了一一岛三岸岸共四块块陆地，陆陆地之间间有七座座桥连通通，如图图6-11(a)所示当时城城内居民民在散步步时热衷衷于这样样一个问问题：从从某陆地地出发，能能否走遍遍七桥且且每桥只只过一次次而最终终回到原原出发地地图6-1（aa）图6-1（bb）欧拉在1

4、7736年年解决了了这一问问题他他用四个个点表示示四块陆陆地，用用相应两两点间的的边表示示桥，从从而建立立了该问问题的图图的模型型，见图图6-11(b)于是是问题归归结为：在这个个连通多多重图中中，能否否找出一一条回路路，过每每边一次次且仅仅仅一次欧拉在在求解该该问题时时，把图图6-11（a）所所示的实实际问题题抽象为为图6-1（bb）所示示图形例6-2 比赛赛安排问问题5个球队之之间安排排赛事其中aa球队分分别与bb，c，dd球队有有赛事；b球队还还与c球队，dd球队还还与e球队有有赛事综上，这这5个球球队之间间的比赛赛关系可可用图66-2(a)来来表示，也也可用图图6-22(b)来反映映图

5、6-2（aa）图6-2（bb）以上两例都都忽略了了问题的的具体细细节，而而把问题题的关键键性质或或关系抽抽象为图图的形式式例66-1中中两岸和和岛的形形状及桥桥的曲直直都被忽忽略，但但陆地间间的关联联情况却却得到保保持例例6-22中把比比赛关系系抽象为为连接关关系简简单些说说，一个个图代表表了某些些对象集集合之间间的关系系，而图图论是主主要研究究这些对对象在上上述表示示法中的的许多可可能的性性质中的的某些性性质详详细些说说，一个个图指的的是一些些点以及及连接这这些点的的一些线线的总体体这种种连接方方式可以以具有许许多特征征，而图图论本质质上就是是研究这这种特征征的注注意，这这里所讲讲的图并并不

6、是解解析几何何与微积积分书中中常见的的图，在在那里，点点的位置置，线的的长度和和斜率是是它的重重要部分分而在在图论中中，这些些都是不不重要的的，而重重要的只只是哪些些点之间间有线相相连有有时，连连接的先先后次序序也是重重要的二、几个基基本概念念1无向图图一个图定义义为一个个有序二二元组（，），记为：（，）其中，V是是一个有有限非空空的集合合，其元元素称为为G的结点点或顶点点，简称称点，而而V称为G的结点点集或顶顶点集，简简称点集集，一般般表示为为：，而E称为GG的边集集，表示示为：，其中由中元元素对(，)所构构成如如果(，)是无序序对，则则称为无无向图中元素素称为的无无向边，一一般表示示为(，

7、)对于给定的的图可以以作出其其几何图图例6-3 无向向图（，），其其中点集集，,，边边与顶点点的关联联情况由由表6-1给出出表6-1 边边与顶点点的关联联情况(，)(,)(,)(,)(,)(,)(,)(,)(,)根据表6-1，可可作其几几何图，如如图6-3所示示在作作几何图图时，仅仅要求表表示出顶顶点、边边以及它它们间的的关联关关系，而而对顶点点的位置置以及边边的曲直直、长短短都没有有任何规规定图6-3基于无向图图的结构构特点，我我们给出出下列一一些术语语：平行边若两条条不同的的边与具有相相同的端端点，则则称与为的平行行边图图6-33中与是平行行边，因因为它们们的端点点均为、简单图若无平行行边

8、，则则称图为为简单图图完备图图中任两两个顶点点间恰有有一条边边相关联联，为完完备图2有向图图设顶点的非非空集合合（，），边边的集合合（，）如如果中任任一条边边是的一个个有序元元素对(，)(这里里，)，则则称为有有向边集集，中元元素称为为有向边边或弧，记记为(，)其中为的起起点，为为的终点点和组成了了一个有有向图，记记作（，）例6-4 给给有向图图（，），其其中（，），（，），边边与顶点点的关联联情况如如表6-2所给给表6-2 边与与顶点的的关联情情况(，)(,)(,)(,)(,)(,)(,)(,)(,)根据表6-2也可可作出有有向图，如如图6-4（aa）图6-4(a)图6-4(b)图6-4（c

9、c）有向图区别别于无向向图的关关键，在在于它的的边（或或弧）是是有方向向的，图图6-44（a）中中边上的的箭头所所指即边边的方向向在有有向图中中(，)(，)类似于无向向图，有有向图也也有下列列术语：平行边不同的的弧与(，)的起点点与终点点都相同同图66-4（aa）中、是平行行边，而而、却不是是，(,)；而(,)简单图无平行行边的有有向图称称为简单单图完备图图中任任两个顶顶点与间，恰恰有两条条有向边边(，)及(，)，则称称该有向向图为完完备图基本图把有向向图的每每条边除除去方向向就得到到一个相相应的无无向图，称称为的基本本图例例如图66-4（bb）是图图6-44（a）的的基本图图3同构对于无向图

10、图和有向向图，如如果图（，）和(，)的顶顶点集合合和，以及及边集EE和E之间在在保持关关联性质质的条件件下一 一对应应，则图图和同构例如图6-2(a)、(b)所示的的两个图图看似不不同，其其实是同同构图由于同构的的图被认认为是相相同的，这这就给我我们在网网络规划划中建立立网络模模型带来来许多方方便，当当我们用用几何图图来反映映和分析析实际问问题的内内在关系系而构建建网络模模型时，点点的位置置可以任任意布置置，边的的长短曲曲直也可可任意，故故而我们们尽量设设计那种种反映问问题清晰晰、简练练的几何何图4链、路路和连通通性给定一个无无向图（，），其其中的一一个点与与边的交交错序列列，如果果序列中中所

11、有都都满足（，），（1，22，1），则则称交错错序列为为联结和和的链，记记为（，）或简记为（，）和（，）当0，且且，则链链的起点点等于终终点，称称为闭链链闭链链中除起起点和终终点外没没有相同同的结点点和边，则则该闭链链称为圈圈当，时称称为开链链若开开链中所所有结点点均不相相同，称称为初等等链例如图6-5中：图6-51（，）是闭闭链，但但不是圈圈；2（，）是闭闭链，同同时也是是圈； 3（，）是开开链；4（，）是初初等链对于有向图图（，），可可以通过过其相应应的基本本图来定定义它的的链但但由于有有向图中中弧是有有方向的的，可能能出现链链中的弧弧的方向向与链的的方向不不一致的的情况如果链链中所有有弧

12、的方方向与链链的方向向一致，则则称该链链为单向向路，简简称路显然，在在有向图图中链和和路的概概念并不不一致，而而在无向向图中两两者没有有区别如果路的起起点和终终点相同同，则称称为回路路对于于无向图图而言闭闭链和回回路概念念一致在图66-4（aa）中：1（，）是链链，但不不是路；2（，）是链链，同时时也是路路和回路路在中任意两两个结点点i1和ik，从从i1到ik存在在路，则则称i11可达ikk若中任任意两结结点间存存在链，则则称为连连通图若中任任意两结结点间相相互可达达，则称称为强连连通图对于无无向图而而言连通通图等价价于强连连通图例如图6-4（aa）所示示的是强强连通图图，因为为、都是相相互可

13、达达的如如果我们们将图中中弧删去去，如图图6-44（c）所所示，则则成为一一般的连连通图因为这这时、不能相相互可达达5网络一个图连同同定义在在其边集集上的实实函数一一起称为为一个网网络网网络一般般是连通通图定定义在边边集上的的实函数数称为边边的权数数记为(，)它与边(，)具有一一一对应应关系，可可以用以以表达网网络上的的各种有有关性质质，如路路长、流流量、费费用等等等网络络的图解解即在每每条边旁旁标上相相应的权权数若一网络的的每条边边都是无无向边，则则称为无无向网络络，记为为（，）或或(，)若一网络的的每条边边都是有有向边，则则称为有有向网络络，记为为（，）或或(，)若一网络中中既有无无向边，

14、也也有有向向边，则则称为混混合网络络所谓网络分分析，简简单地说说，即对对网络进进行定性性和定量量分析，以以便为实实现某种种优化目目标而寻寻求最优优方案这方面面的典型型问题有有：最小小树问题题，最短短路问题题，中心心问题，重重心问题题，最大大流问题题，最小小费用最最大流问问题，最最短回路路问题，网网络计划划问题，等等等第二节 最最小树问问题一、树的基基本概念念1子图、真真子图、生生成子图图设有图(，)和图图(，)，如如果，则称称为的子图图，并记记为，而而则为的原原图当当子图的的边集或或点集不不同于原原图时，即即时，称称子图为为的真子子图，记记为当当子图的的点集等等于原图图的点集集时，则则称子图图

15、为原图图的生成成子图或或支撑子子图在图6-66中，（aa），（bb），（cc），（dd）均是是（a）的子子图；（a），（b），（c）是（a）的真子图；（a），（b），（c）均是（a）的生成子图由于（d）比（a）少一个点，所以（d）不是（a）的生成子图图6-62树无圈且连通通的无向向图称为为树树树一般记记为作作为树定定义还可可以有以以下几种种表述：(1)连通通且无圈圈或回路路；(2)无圈圈且有nn1条条边（如如果有nn个结点点）；(3)连通通有n1条条边；(4)无回回路，但但不相邻邻的两个个结点之之间联以以一边，恰恰得一个个圈；(5)连通通，但去去掉T的任意意一条边边，就不不连通了了；(6)的任

16、任意两个个结点之之间恰有有一条初初等链二、最小生生成树及及其算法法1最小生生成树如果是无向向图的生生成子图图，同时时又是树树，则称称是的生成成树或支支撑树例如图6-7（bb），（cc）是（aa）的生生成树图6-7一个网络图图可以有有多个生生成树记N的所有有生成树树的集合合为： | 1，22，L 设（，）是是网络图图N（，）的一一棵生成成树，则则边集中中所有边边的权数数之和称称为树的的权数，记记为（）若，使（）（）则称为网络络的一棵棵最小生生成树，简简称最小小树2最小树树的求法法定理8-11如果把把网络的的点集分分割成两两个不相相交的非非空集合合和，则联联结和的最小小边必包包含于NN的最小小树内

17、根据定理88-1，可可以给出出求最小小树的两两种方法法，这就就是避圈圈法与破破圈法，分分述如下下：(1)避圈圈法其计算步骤骤如下：从网络中中任选一一点，令令，；从联结与与的边中中选取最最小边，不不妨设为为(，)，则则它必包包含于最最小树内内；令，；若，则则停止，已已选出的的诸边即即给出最最小树；否则返返例6-5试求图图6-88所示网网络的最最小树，各各边旁边边的数字字为各边边的权图6-8解由题意意可知这这是一个个最小树树问题先按原原图画出出7个点点，令1，2，33，4，55，6，77由由于联结结与的边共共有三条条，其中中最短边边为(11，2)故用线线把点11和2连连结起来来，令1，22，3，4

18、4，5，66，7，如图图6-88(a)所示，重重复上述述步骤，直直到7个个点全都都连通为为止具具体求解解过程如如图6-8（aa）到图图6-88（f）所示示，其中中图6-8（f）)即即给出本本例的最最小树，()113图6-8（aa）（bb）图6-8（cc）（f）(2)破圈圈法用破圈法求求最小树树时，先先从图中中任取一一圈，去去掉该圈圈的一条条最大边边，然后后重复这这一步骤骤，直到到无圈为为止例6-6 图6-99所示的的一赋权权连通图图是某一一具有99个居民民点的交交通网络络图，其其中边权权表示该该段道路路的长，现现欲沿小小区道路路架设一一联络各各个居民民点的闭闭路电视视系统，求求可使闭闭路电视视

19、系统所所架线路路总长最最短的方方案图6-9解 这是是一个求求网络最最小树的的问题可利用用破圈法法求解过程如如图6-9（ai）所示示图6-9（aai）图6-9（ii）所示示的是网网络最小小树按按图安排排闭路电电视系统统可使所所架线路路总长最最短，()119第三节 最最短路径径问题在生产实践践，运输输管理和和工程建建设的很很多活动动中，诸诸如各种种工艺路路线的安安排、厂厂区及货货场的布布局、管管道线网网的铺设设及设备备的更新新等等问问题，都都与寻找找一个“图的最最短路径径”问题(shoorteest-patth pprobblemm )密切切相关，它它是网络络规划中中的一个个最基本本的问题题一、基

20、本概概念给定一个赋赋权有向向图(，)，对每每一条弧弧(，)，相应应地有权权（），又又有两点点、V，设是中从到的一条条路，路路的权是是中所有有弧的权权之和，记记为()最短短路问题题就是求求从到的路中中一条权权最小的的路：()()二、最短路路问题的的算法1Dijjksttra算算法(Dijjksttra alggoriithmm)该算法是由由Dijjksttra于于19559年提提出来，用用于求解解指定两两点之间间的最短短路，或或从指定定点到其其余各点点的最短短路，目目前被认认为是求求解最短短路问题题的最好好方法算法的的基本思思路基于于以下原原理.定理6-22若是从到的最短短路，是是中的一一个点，

21、那那么从沿沿到的路必必定是从从到的最短短路引理若是是从到的最短短路，是是中的一一个点，则则从到的最短短路必定定包含于于之内根据定理66-2及引引理，我我们可以以从s出发试试探所有有可能到到达t的下一一个结点点i，取距距离最短短的一个个弧（，），则则必然包包含于从从到的最短短路中；从开始始对没有有试探过过的结点点进行进进一步的的试探、推推进，直直至，最最终可以以找出从从到的最短短路DDijsstraa算法采采用（双双标号法法）T标号与与P标号，来来实现这这一试探探、推进进过程T标号为为试探性性标号；P为永久久性标号号给点点一个PP标号时时，表示示从到点的最最短路权权，一旦旦点得到到P标号则则意味

22、着着从到点的最最短距离离已经确确定，标标号不再再改变给点一一个T标号时时，表示示从到点的估估计最短短路权的的上界，这这是一种种临时标标号凡凡没有得得到P标号的的点都有有T标号算法每每一步都都把某一一点的TT标号改改为P标号，当当终点得得到P标号时时，全部部计算结结束Dijsttra算算法基本本步骤：(1)给以以P标号，PP()0，其余余各点均均给T号，T()(2)若点点为刚得得到P标号的的点，考考虑，(，)A且为T标号对的T标号进进行如下下的更改改：T()mminT()，P() (6-1)(3)比较较所有具具有T标号的的点，把把最小者者改为P标号，即即：P()mmin T() (66-2)当存

23、在两个个以上最最小者时时，可同同时改为为P标号(4)若全全部点均均为P标号，则则停止计计算否否则用代代替并转转至步骤骤（2）例6-7用Dijjksttra算算法求图图6-110中从从到的最短短距离，以以及相应应的路线线图6-100解（1）首首先给以以P标号，PP（ ） 00，给其其余所有有点T标号，TT（i）（i = 2，3， 7）（2）考察察，由于于（，），（，），（，）A，且、是T标号，所所以修改改T标号为为：T（）mmin TT（），P（） minn ，022T（）mmin TT（），P（）minn ，055T（）mmin TT（），P（）minn ，033在所有T标标号中，T()2最小

24、，于是令P()2将结果记在图6-10（a）上：P标号以（）形式标在结点旁边，T标号以不带（）的数字标在结点旁边，图中没有标号的结点均代表T（）(3)考察察因为为（，），（，）A，且、是T标号，故故、新的T标号为为：T（）mmin TT（），P（）minn ，224T（）mmin TT（），P（）minn ，279在所有T标标号中，T()3最小，故令P()3图上标号如图6-10（b）(4)考察察，因（，）A，T（）mmin TT（），P（）minn ，358在所有T标标号中，T()4最小，令P()4图上标号如图6-10（c）(5)考察察，（，），（，）A，T（）mmin TT（），P（）minn

25、 ，437T（）mmin TT（），P（）minn ，459在所有T标标号中，T()7最小，令P()7图上标号如图6-10（d）(6)考察察，（，），（，）A，T（）mmin TT（），P（）minn ，718T（）mmin TT（），P（）minn ，7714在所有T标标号中，T()8最小，故令P()8图上标号如图6-10（e）(7)考察察，（，）A，T（）mmin TT（），P（） minn 114，8513令P()13，图图上标号号如图66-100（f）所所有点都都标上PP标号，计计算结束束从到的最短短路径，可可从开始始根据永永久性标标号数值值回溯得得到最最短路径径是：，路长长13同同时

26、得到到到其余余各点的的最短路路，即各各点的永永久性标标号P（i）Dijksstraa算法只只适用于于所有00的情形形，当赋赋权有向向图中存存在负权权时，则则算法失失效图6-100（a）（b）（c）（d）（e）（f）2逐次逼逼近算法法为方便起见见，不妨妨设从任任一点到到任一点点都有一一条弧，如如果在中中，不存存在弧(，)，则添添加虚设设弧(，)，令从起起点到任任意点的的最短路路可以视视为一个个两阶段段过程，如如图6-11所所示：图6-111(1)从出出发，沿沿着一条条路走1步到某某点，其其最短距距离表示示为(，)(2)再从从沿(，)到，其最最短距离离就是弧弧(，)上的权权 所以，从到到的最短短距

27、离必必满足如如下递推推公式：(，)（1，2，n） （66-3）(，)(，) （66-4）式（6-33）是任任意两点点间的一一步距离离，由前前面假设设可知其其存在，这这可以作作为初始始条件式（66-4）是是任意两两点间的的k步距离离，这是是一个递递推公式式利用用初始条条件和递递推公式式通过逐逐步迭代代就可以以确定网网络中任任意点之之间经步步到达的的最短距距离并得得到与之之相应的的路线下面以以实例来来说明迭迭代过程程例6-8用逐次次逼近算算法求例例6-66图6-10中中从到各各点的最最短距离离解根据初初始条件件可知(，)00(，)2(，)5(，)33(，)(，)(，)；初始条件仅仅仅表达达了从出出

28、发到的的一步到到达的距距离，在在有向简简单网络络中即为为从到各各点的最最短距离离到各点的步步距离由由公式（66-4）递递推得出出为方方便、直直观可列列表计算算如表66-3：表6-3到各点点的步距距离jvii(，)(，)k=1k=2k=3k=4k=5k=60253000000027222222013554444405333333017877770598880141313表的左半部部是一个个nn的关于于结点两两两之间间的一步步距离矩矩阵，由由式（66-3）可可知，到到的一步步距离就就是弧（，）上的权一步距离矩阵中0元素表示原地踏一步，没有填写数字的空格是的省略表右半部是公式（6-4）的计算结果k=

29、h时，第h+n列数据表示到各点的h步最短距离譬如k=3为第 列，表示经3步到达各点的最短距离计算过程如下：（1）当kk=1时(，)这是初始条条件，表表示从出出发到各各点的一一步距离离，将其其依次列列于第 列由由此推算算(，)（2）k=2时(，)(，)即用表中第第 列数数字与表表左边一一步距离离矩阵中中第列相相应数字字相加取取小，得得到从出出发到各各点的二二步距离离：（0 00）（ 2）（ 5）(，)mmin （ 3） 0（ ）（ ）（ ）（2 00）（0 2）（ 5）(，)mmin （ 3） 2（ ）（ ）（ ）同理： (，)4(，)3(，)8(，)(，)得：024(，) 338将其填入表表6

30、-33第 列（3）重复复上述步步骤得到到(，)、(，)、(，)、(，)；分别别填入表表6-33第 、 列（4）当kk=6时，发发现(，)(，)，说明明对于整整个有向向图D而言，继继续增加加步数已已不起作作用，即即已得到到从到各各点的最最短距离离，即表表中 或 列数数字：0；原地地一步2；一步步到达4；二步步到达3；一步步到达7；三步步到达 8；四四步到达达 13；五五步到达达从表6-33中还可可以用回回溯方法法推知到到各点最最短距离离的相应应最短路路线，以以到为例：由第列行行可知，到经5步到达，最短距离13回溯13的来源：（，）=113因（，） 列行 列行 （，）8513故记下（，）因（，）

31、列行 列行 （，）718故记下（，）.因（，） 列行 列行 （，）437故记下（，）因（，） 列行 列行 （，）224故记下（，）因（，）022，记下下（，） 得到最短路路径：当网络图存存在负权权时，DDijkkstrra算法法失效，必必须采取取逐次逼逼近算法法来求解解最短路路例6-9试求网网络图66-122中到各各点的距距离图6-122解初始条条件：(，)0(，)1(，)(，)2(，)(，)计算结果如如表6-4所示示：表6-4到各点点的距离离vjvi(，)=1=2=3=4=501200000034111-1-1-2051411140-322222330-1-1-1-120求得到各点点的最短短

32、距离：(，)00；原地地一步(，)-1；四四步到达达(，)11；三步步到达(，)22；一步步到达(，)-1；二二步到达达(，)；无法法到达逐次逼近算算法，因因其类似似于矩阵阵乘法，在在有些书书籍表述述为距离离矩阵摹摹乘法，它它们的实实质一致致这种种算法在在n个结点点的网络络图中，至至多经过过n-1次次迭代必必然收敛敛但前前提条件件是图中中不含有有总权小小于0的的回路，否否则最短短路权没没有下界界第四节最最大流问问题网络流(nnetwworkk fllow)是一类类普遍存存在的现现象例例如在交交通运输输网络中中有人流流、车流流、货物物流；供供水网络络中有水水流；金金融系统统中有现现金流；通讯系系

33、统中有有信息流流；等等等在220世纪纪50年代代Forrd和Fullkerrsonn建立的的“网络流流理论”是网络络应用的的重要组组成部分分网络最大流流问题(maxx-fllow proobleem)尤为重重要这这是因为为绝大部部分网络络流研究究，旨在在寻求在在一定条条件下使使网络流流达到最最大的方方法如如图6-13是是输油管管道网，为起点，是终点，为中转站，弧上的数表示该管道的最大输油能力，问应如何安排各管道输油量，才能使从到的总输油量最大?图6-133一、基本概概念和基基本定理理1网络流流所谓网络流流，是指指在一定定的条件件下流过过一个网网络的某某种流在在各边上上的流量量的集合合表达达为(

34、，)| (，)所谓一定条条件，一一般是指指如下规规定：(1)网络络有一个个始点和和一个终终点，始始点是流流的源，终终点是流流的汇；(2)流具具有一定定的方向向，流经经各弧的的流，其其方向就就是相应应弧的方方向；(3)对每每一弧(，)，都赋赋予一个个容量(，)0，简记记为，表示容容许通过过该弧的的最大流流量并并称(，)为通过过弧(，)流，简简记为凡做出上述述规定的的网络都都可称为为容量网网络，记记为（，）图6-133所示的的就是一一个容量量网络图中每每条弧上上的数对对为(，)，标明明了弧的的容量以以及流经经该弧的的流量2可行流流和最大大流可行流是指指满足容容量限制制条件和和平衡条条件的流流(1)

35、容量量限制条条件：对对于任一一弧(，)，都有有0，即任任何弧上上的流量量不能超超过弧的的容量(2)平衡衡条件：对于任任一中间间点，都都有即每个中间间点的流流出量必必须等于于流入量量，其净净流量为为0对于始点和和终点，有有即始点流出出量等于于终点的的流入量量，这个个流量即即是可行行流的流流量，记记为（）所谓最大流流问题，就就是在可可行流恒恒存在的的前提下下，满足足max () . 00 、0； 这是一个特特殊的线线性规划划问题，可可用单纯纯形法求求解但但用图形形方法求求解更为为直观和和简单3增广链链如果是网络络中联结结始点和和终点的的一条链链，且链链的方向向从到，则与与链方向向一致的的弧称为为前

36、向弧弧，用来表示示前向弧弧集合；与链方方向相反反的弧称称为后向向弧，用用来表示示后向弧弧集合如图6-113中(，)，(，)，(，)(，)，(，)设是一个可可行流，是一条从到的链，若满足下列条件，则是可行流的一条增广链：（1）在弧弧(，)上， 00；（2）在弧弧(，)上， 00这就意味着着在增广广链上每每一个前前向弧的的流量都都没有达达到最大大容量（即即不饱和和前向弧弧）,而每一一个后向向弧的流流量均不不为0（即非非零后向向弧）如图6-113中链链、 、 都是增增广链可以指指出，沿沿增广链链调整各各弧的流流量可以以使网络络流量（）增大大，而寻寻求网络络最大流流的方法法正是以以增广链链为基础础的4

37、截集与与截量在一个网络络(，)中，若若把点集集V剖分成成不相交交的两个个非空集集合和，使，且中各各点不须须经由中中的点而而均连通通，中各各点也不不须经由由中的点点而均连连通，则则把始点点在中而而终点在在中的一一切弧所所构成的的集合，称称为一个个分离和和的截集集，记为为(，)截集集实质上上是网络络从到通路的的横截面面表达，它它反映了了网络从从到的必经经之路一个网网络可以以有多个个截集，表表6-55反映了了图6-13网网络的截截集集合合表6-5图66-133网络的的截集集集合S截集(S，)=(，)截量(S，)s1,2,33,4,t(s,1), (s,22)14s,12,3,44,t(s,2), (

38、1,22), (1,3), (11,4)15s,21,3,44,t(s,1), (2,44)14s,1,223,4,tt(1,3), (1,44), (2,4)12s,1,22,32,4,tt(s,2),(11,2),(11,4),(33,4),(33,t)19s,2,441,3,tt(s,1), (4,tt)16s,1,22,34,t(1,4), (2,44), (3,4), (33,t)16s,1,22,43,t(1,3), (4,tt)11s,1,22,3,4t(3,t), (4,tt)13给定一截集集(，)，其中中所有弧弧的容量量之和称称为这个个截集的的截量，记为(，)|（，）(，)一

39、个网络可可以有多多个截集集和截量量，其中中截量最最小的截截集称为为最小截截集，记记为(，)，其截截量称为为最小截截量(minn-cuut)，记为(，)图6-133的最小小截量由由表6-5看出出为111，最小小截集为为(，)(11,3), (4,tt)二、基本原原理为了介绍一一种寻求求网络最最大流的的标号法法，这里里将阐述述其原理理定理6-33（流量量截量定定理）在网络络=(，)中，设设为一可可行流，(，)是任一截集，则（）(，)定理6-33表明，网网络的任任一可行行流的流流量恒不不超过任任一截集集的截量量因此此，网络络的最大大流量也也不会超超过最小小截量定理6-44（最大大流量最最小截量量定理）网络中中从s到t的最大大流的流流量等于于分离ss和t的最小小截集的的截量即，（）(，)定理6-44实际上上是定理理6-33的推论论定理6-55（最大大流的充充要条件件）设设是网络络(，)的一个个可行流流，则为为最大流流的充要要条件是是：网络络中不存存在关于于的增广广链()定理6-66（增广广链调整整法）设是(V，AA，)的一个个可行流流，是关关于f 的一条条增广链链令 当 当 当 （6-5） 当min（，）构造一个新新的可行行流，令令 当（，） 当（，） （66-6） 当（，）则()也也是的一一个可行行流，其其流量为为（）（） （6-7）