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

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