网络规划教学讲义教案.docx

第十一章 网络规划11.1最小生成树问题：现实生活中有许多类似在城镇间架设的电话线、铺设管道、修筑道路的问题,通常在一些早期的发展阶段，由于技术或财力的局限，人们总是从节省材料或资金的角度，试图设计一个网络能够使得不同城镇均能被直接或间接的连接起来，使其总长度最短。1几个补充概念：l无向图与有向图；子图；（无向图）链与初级链、圈与初级圈；（有向图）路与初级路、回路与初级回路；连通图（这些概念或参阅图论方法建模或参考专门的参考书）；l树：无向图是一个无圈的连通图，则称之为树；l树的性质：1)树的边数等于其顶点数减“1”，即；2)树的任意两个顶点之间恰有一条初级链相连接；3)在树中任意去掉一条边后，便得到一个不连通的图；4)在树中任意两个顶点之间添加一条新边，所得新图恰有一个初级圈。l根树：有向图，若，对，都存在唯一的一条从顶点到顶点路，则称有向图为一根树，顶点为根。l根树的性质：1)对，都存在唯一的一条从根到顶点路；2)根不是任一条有向边的终点，而对，顶点恰是根树的一条有向边的终点；3)根树相对于它的基础图（不考虑边的方向，对应的无向图）树，它由根唯一确定。图 以为根的根树l赋权图：若图中各边都赋有一个实数(称为权),则称该图为赋权图，这里记之为2最小生成树问题在一个赋（边）权连通图中寻找一棵生成树（的边集记为），使这棵树各边的权相加所得和（也称为之权）最小.称中权最小的生成树为的最小生成树.3.算法思想:把的条边按权的递增顺序排列,再依次检查每条边是否入选.设当前要检查的边为,而已选中的边组成的集合为.如果图中无圈,则选入;否则不选,而继续检查下一条边.给的每个顶点根据当前的边集的组成状况定义一个标号,使具有特性:当且仅当在图中存在一条连接顶点与的链时,有.定理若当前检查的边不属于,则在时,图中必定有圈;在时,中必定无圈.4.算法1)将的条边按权的递增顺序排成序列:，取.2)边的端点的标号与相等否? 若是:取,转(2)；若否:取.3)对一切满足的,取(即保证中所在连通块中,各顶点新标号都相同).4)中元素个数(即边数)? 若是:算法终止；若否:取,转(2)。5.定理设为一个赋权的连通图,为应用算法所得的边集,则必为的一棵最小生成树.证明：设，不妨设，；取满足：；为的一棵最小生成树；在的所有最小生成树中，的边集合与的交集所含元素个数最大。以下证明只能是：假设不然，则存在某数，满足、,根据算法及假设，必有，进而。根据树的性质，在上加一边后，含一个初级圈，显然应含边；另一方面根据算法，中无初级圈。因此，所含的初级圈除含边外，也应有，不妨含某边，其中，此时的权不比的大，但含中的边数比多“1”，这与题设“在的所有最小生成树中，的边集合与的交集所包含元素的个数最大”矛盾。即必有，这时必为的一最小生成树。6.破圈法算法的思想是将图的全部边按照边权的大小从大到小排序，在原图的基础上，从前到后考察这些边，每考察一边，验证是否存在包含该边在内的初级圈。若有，将该边从边集中删除，否则保留。直到剩余子图为一树（可以以剩余的边数作为检验条件），否则在考察下一条边。按照这一思想构造的求解最小生成树的算法被称为“破圈法”（而称算法为“避圈法”），你可以仿照算法给出“破圈法”的准确刻画。例、下图为一连通的赋权图，求其最小生成树.11.2最大流问题问题（输油管网络问题）：在一个输油管网中，有生产石油的油井、储存石油的油库、转运石油的中间泵站，同时，还有各种口径不同的输油管。当一个输油管网给定后，单位时间内最多可把多少石油从油井输送到油库？具体方案如何？图11.2.11网络概念：设是一个顶点集，是中两个不同的顶点，是有向边集合，中每条有向边都对应一个正（整）数，称为的容量，则赋权有向图称为一个网络，其中称为的源，称为的汇。记、而就输油管网络问题，可用顶点表示油井、油库和中间泵站，用有向边表示输油管，用有向边上的权表示单位时间沿相应的输油管可以输送石油的最大数量。则得输油管网，源和汇分别表示油井和油库。2网络流的概念：设是网络的边集上一个非负（整数）函数，它满足下面两个条件：、，则称为网络上的一个流，其中条件(1)称为容量约束，条件(2)称为守恒条件。把称为流的流值，记为。网络中流值最大的流称为的最大流。、图11.2.2、而就输油管网络问题，表示单位时间沿输油管实际输送石油的数量，的容量表示单位时间沿输油管输送石油的最大允许量，故有。对于中顶点，单位时间内输送到的石油量是以为终点的所有有向边上的输送量之和，即；单位时间内从输出的石油量是以为起点的所有有向边上的输送量之和，即。由于中间泵站仅起转运石油的作用，故对非源非汇的顶点，有。、图11.2.33最大流问题是一类特殊的线性规划问题l决策变量：；l目标函数；l约束条件：；4增量网络：称为网络关于流的增量网络，若：（1）.，；（2）.，正向（正规）弧集；反向（正规）弧集；（3）.图11.2.45网络割的概念：设为一个网络，而且，则边集为中起点和终点的全体有向边组成的集合，即。如果是的一个子集，,则称边集为网络的一个割，而称为割的容量。网络中容量最小的割称为的最小割。而就输油管网络问题，设为网络的一个割。令，它表示单位时间通过割实际输送石油的数量。图11.2.5 理解割的概念6定理：设和分别为网络的流和割，则有：（1）.；（2）.若，则和分别为网络的最大流和最小割；（3）.在中。7流关于路的修改流：设是网络的一流，为网络关于流的增量网络，为中到的一路，称为路的容量，定义关于路的修改流如下：l这时8定理：设是网络的一流，为网络关于流的增量网络：（1）.是网络的最大流中不存在从到的路；（2）.的最大流和最小割均存在，且。9最大流算法：（1）.给出初始流，并网络关于流的增量网络；（2）.搜索中从到的容量尽可能大路，若不存在，是网络的最大流，停；（3）.令，给出网络关于流的增量网络，转（2）。l为准确理解以上算法,可试着计算图11.2.1从顶点到顶点的最大流.4搜索中从到的容量尽可能大路，（以为根的最“大”生成根树）：（1）.令，(),给出割；（2）.若，停，中不存在从到的路；（3）.取，(或)，,；（4）.若，停，输出路，否则，给出割，转（2）.例. 搜索以下网络中从到的容量尽可能大路11.3最短路问题：在现实生活当中，有许多问题类似我们在假日旅行时，当目的地确定后，我们常常为了缩短行程或者节省开销而选择一条总路程或总开销最小的旅行路线。1设是一个赋权有向图，且其中每条有向边的边权均为非负实数，。现要求出中顶点与任一顶点的距离，当时求出中到的最短路。l路的权：;l最短路：设为到的路满足，则称为到的最短路;l到的距离：.2定理：设是一个赋权有向图，且其中每条有向边的权均为正数，设为到的最短路，则必为一初级路，即不含圈。证明：设为到的最短路，且中含圈，即，满足，此时，由已知“是一个边权均为正数的赋权有向图，为到的路，且，这与假设“为到的最短路”矛盾。考察如下赋权有向图：图11.3.1图11.3.1(a)、(b)、(c)分别为中从顶点、到其它各顶点的最短路，它们分别是以、为根的根树（当然不包括距离为的顶点）。以下讨论在中顶点到其它各顶点的最短路：3算法思想：在“让小的顶点优先生长的原则”，每步生长一个顶点，由最短路的性质，可取中到的最短路（）：为初级路，且若顶点在上，则上到部分就为到的最短路。从而组成一个以为根的根树（若则不包含）。图11.3.2例，图11.3.2(a) 是一个边权均为非负实数的赋权有向图；图11.3.2 (b) 为该网络图中顶点到其它各顶点的最短路组成的一个以为根的根树，每个顶点旁括号内的数字为到的距离。因为根树中根到各顶点的路唯一。可从根逐步生长根树，采用“让小的顶点优先生长的原则”，每步生长一个顶点。第步（即第个顶点）的生长过程。设上已有个顶点：（为第步长到上的顶点），现在余下的个顶点中确定一个顶点。顶点显然应具有下列两个性质：(1)应是余下的个顶点中离最近的顶点.(2)若存在到的最短路,则可以是一条初级路,且上除顶点尚不在中外,其余顶点都已在中.设为中到的一条初级路(不在中),而且中顶点除外均已在中.用表示这种中最短者,用表示它的权(当不存在时,),显然,可按照如下方式来确定:而且还有.问题是,如何计算?易知,到的初级路可分成两类:(1)不包含顶点.故在这类路中最短者的权为;(2)包含顶点.由于为中与距离最大的顶点.故若为这些初级路中的最短者,则在中必为之紧前顶点.所以的权应为.于是有.初始时仅包含顶点,故初始条件可如下规定:.又应用迭代公式,可以确定根树的生长序列.4算法:（1）.取定初始条件,取；（2）.是:根据应用逆向追踪法,求得所需的最短路,算法终止；否:取（对）；（3）.确定：并取；（4）.?若是:取,转(2)；若否:中到的路都不存在,根据应用逆向追踪法可求得中到的最短路,算法终止。设是中的紧前顶点,显然应有,且.利用该性质并根据所求得的,从而通过逆向追踪而求得各条最短路.l算法（的另外一种表述）:（1）.取定初始条件：，,；（2）.若算法终止；否则:对取，若，令；（3）.确定：并取.（4）.若，取,转(2)；否则:中到的路都不存在，算法终止。5定理：设是一个一个赋权有向图，且其中每条有向