[高等教育]第l六章运筹学图与网络.ppt

图的基本概念与模型 树图和图的最小部分树 最短路问题 网络的最大流,第五章 图与网络模型(Graph and network modeling,教学目的与要求:给学生建立起用图建模的思想,学会用图分析问题. 重点与难点:图的各种概念,最短路的求法,最大流的求法,其中难点是最大流的求法. 教学方法:课堂讲授结合WinQSB软件的使用. 思考题,讨论题,作业:本章习题. 参考资料:见前言. 学时分配:8学时.,序言,哥尼斯堡七桥问题:,德国的哥尼斯堡城有一条普雷格尔河,河中有两个岛屿,河的两岸与岛屿之间有七座桥相互连接.当地居民热衷于一项活动,一个散步者如何能走过这七座桥,且每座桥只能走一次,最终回到出发地.试验者很多,但没有人才成功.,1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文,解决了著名的哥尼斯堡七桥问题.,欧拉将哥尼斯堡七桥问题抽象成如下的图形:,哥尼斯堡七桥问题变为,能否从图的某一点开始不重复地一笔画出这个图形.你能一笔画出吗?,欧拉在论文中证明了这是不可能的.为什么?,理由是:图上的每一个顶点都与奇数条边相连接,不可能一笔画出.,第一节 图的基本概念与基本定理,一.图的基本概念,日常生活中我们见过大量的图,如各种交通图, 各种管网图(电网图,自来水管网,煤气管网,计算机网络).都是用点表示研究对象,用线(边)表示这些对象间的关系.因此,图可以定义为点和边的集合.记作G=V,E,其中V是点的集合,E是边的集合.在图的点和边上赋予权值(如距离,费用,容量等)则称这样的图为网络图记为N,网络图又可分有向网络图和无向网络图.,名词介绍:,图中的点用v(vertex)表示,边用e(edge)表示,每条边用它联结的点表示,如,端点,关联边(incident),相邻(adjacent): 若有边e可表为 称 为边e的端点;称边e 为 的关联边;若点 与同一条边关联,称点 相邻;若边 有公共的端点,称边 相邻.,图一,环(loop)多重边,简单图:如果边e的两个端点相重,称该边为环,如 .如果两个端点之间多于一条边,称它具有多重边,如 对于无环无多重边的图称为简单图.,次,奇点,偶点,孤立点,悬挂点:与某一点 相关联的边的数目,称为点 的次,记为 如 次为奇数的点称为奇点,否则称为偶点,次为1的点称为悬挂点,次为0的点称为孤立点.,链(chain),圈(cycle),路(route,path),回路,连通图:图中某些点和边的交替序列,若其中各边 互不相同,且对任意的点 均相邻,称之为链.,如果链中所有的顶点各不相同,这样的链称为路.,判断 哪一个是链,哪一个是路:,对起点和终点相重合的链称为圈.起点和终点重合的路称为回路.在一个图中,如果任意两点间至少存在一条链,则称该图为连通图,否则为不连通的.,完全图,子图,支撑子图(部分图),一个简单图中,如果任意两点之间均有边相连,称为完全图.,例1 有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到每名运动员不连续参加两项比赛.,解:把比赛项目看作研究对象,用点表示.如果两个项目没有同一名运动员参加,表明它们在比赛顺序上可排在一起,在代表这两个项目的点之间连一条线,得一图形.在该图中找一条包含全部顶点的路,就是符合要求的比赛顺序.,结果:比赛顺序是A,C,B,F,E,D.,练习1 有甲,乙,丙,丁,戊,己六名运动员报名参加A,B,C,D,E,F六个项目比赛.报名情况如下表,问六个项目的比赛顺序如何安排,做到每名运动员不连续参加两项比赛.,练习2 有八种化学药品A,B,C,D,P,R,S,T要放进储藏室保管,出于安全原因,下列各组药不能放在同一室内,A-R,A-C,A-T,R-P,P-S,S-T,T-B,B-D, D-C,R-S,R-B,P-D,S-C,S-D,问储藏这八种药至少需几间房?具体的放置方法是什么?,第二节 树和图的最小部分树(最小生成树) (Tree and minimal spanning tree),树的定义:无圈的连通图称为树,记为T=(V,E).,铁路的转用线,管理机构图,学科分类图,AHP决策方法等,都可用树来表示.,树的特点:1.树是边数最多的无圈连通图,即在树上再任意增加一条边,必定出现圈;,2.树的任意两点间,有一条且仅有一条通路.也可以说,树是最脆弱的连通图,只要在树中去掉任一条边,图就不连通了.,图的最小部分树(最小生成树):设 是一个图,如果 是 的支撑子图(部分图),且 是一个树,则称 是 的部分树.树的各条边称为树枝.在图的每条边上赋予权值的图称为赋权图.,在 中一般含有许多部分树,其中树枝总长为最小的部分树,称为该图的最小部分树.,部分树,部分树,图,最小部分树的求法 方法一:避圈法,例2 如图S,A,B,C,D,E,T代表村镇,村镇之间的连线上赋予了权值(可代表距离,费用,流量等)现沿图中连线架设电线,使各村镇全部通电,问如何架设使电线总长最短.(该图称为赋权图或无向网络).,最小生成树总长=2+2+1+3+1+5=14,方法二:破圈法,在无向网络图N中任取一个回路,去掉这个回路中权数最大的边,得一新网络 ,在 中再任取一回路,去掉这个回路中权数最大的边,得 . 如此继续下去,直到剩下的子图中不再含回路为止,最后的这个子图为N的最小部分树.,电线总长=2+2+1+3+1+5=14,第三节 最短路(Shortest path)问题,最短路问题是指在给定的网络(有向图和无向图)中,找出任意两点间距离最短的一条路,这里的距离是权值的代表.最短路问题可应用于选址,管道铺设时的选线,设备更新,投资等方面. 本节介绍从某一点到其他各点之间最短距离的 Dijkstra算法和网络图上任意两点的最短距离的矩阵算法.,一.无向图最短路的Dijkstra算法(1959),基本思想:最短路的子路一定还是最短路.,Dijkstra标号法的步骤:,0,2,4,4,7,8,13,例3 用狄克斯屈拉标号法求S到T的最短路.,在用WIQSB 时，编号要按从左到右的顺序。,例4 设备更新问题 某企业使用一台设备,在每年年初企业领导决定是购置新的还是继续使用旧的.其购置费和维修费如下表.制定一个五年内的设备更新计划,使总费用最少.,解:用点 表示”第i年年初购进一台新设备”这种状态,增设一点 表示第五年年底.从 到 各画一条弧 i=1,2,3,4,5.弧 表示在第i年年初购进的设备一直使用到第j-1年年底或第j年年初.每条弧的权值可根据表中的数据算出.,用标号法算出从 到 的一条最短路:,两个最优方案分别是: 第一方案:第一,三年各买一台新设备,总费用为53(万元); 第二方案:第一,四年各买一台新设备,总费用为53(万元).,二.有向图的最短路问题,例5 求 到各点的最短路.,解:1.先给顶点 标号(0,0),第一个数字表示从起点到该点的长度(权值),第二个数字表示该点的标号是从哪个相邻的顶点得到的,一般地表为 ;,例5 求 到各点的最短路.,计算过程:,三.求网络各点间最短距离的矩阵算法,例6 求下面网络中各点间的最短距离.,定义: 为图中相邻两点间的距离,若i和j不相邻时,从i到j的路不一定是从i直接到j,它可以是从i出发经过许多中间点到达j.如从S到B,如果只考虑经过一个中间点时,则其最短距离是下列诸距离中的最小值,即,一般可写为 于是构造一个新矩阵,例如: 就是S到T的最短距离,与前边计算结果相同.,例7 如果例6中的七个点表示七个村镇,他们要联合办一所小学,各村小学生人数分别是 S-30,A-40,B-20,C-15,D-35,E-25,T-50. 问小学建在哪一个村镇,使小学生上(下)学走的总路程为最短.,解:将 中第一行各数字乘S村小学生人数,这些数表示小学建在各村时,S村小学生所走的路程,同理可得出下表,小学应建在E村.,第四节 网络的最大流(Maximal flow of network),流(Flow)就是将目标由一个地点运送到另一个地点.如:公路中的交通流,控制系统中的信息流,供水系统中的水流,金融系统中的现金流,邮政系统中的信件流,等等.它们的共同问题是,希望经过输送系统,将目标从一个地点运送到另一个地点的运输量最大,或者将一定数量的目标在该系统中从一个地点输送到另一个地点的费用最小.这就是网络中的最大流问题和最小费用最大流问题.,一.网络最大流的概念,1.有向图和容量网络:有向图是指网络图中的连线是有规定方向的称为弧(arc),记为 它表示弧的方向是从 有向图就是点与弧的集合. 容量网络是指对网络上的每一条弧,都给出一个最大的通过能力,称为该弧的容量,记为 或简记为 ,这样的网络称为容量网络. 在容量网络中规定一个发点(源点)s和一个收点(汇点)t,其余的点称为中间点. 网络的最大流是指:网络中从发点到收点之间允许通过的最大流量.,我们只研究一个发点和一个收点的情况.对于多个发点和多个收点的情况可将若干个发点合并为一个新的发点对于收点也如此处理.,2.流和可行流:流（flow）是指加在网络上的一组负载.对加在弧 上的流,记为 或简记为 ,当 时称为零流.,可行流（feasible flow）：在容量网络上满足下列三个条件的一组流称为可行流 (1) 容量限制条件:对所有的弧有,(2) 中间点平衡条件:,(3) 若以v(f)表示网络中从s到t的净输出量,则有,任何容量网络上一定存在可行流,因为零流就是可行流.,定义:所谓求网络最大流,就是指在满足容量限制条件和中间点平衡条件下,使v(f)值达到最大.,二. 割和流量:在下图中,括弧外的数字表示最大通过量,括弧內的数字为负载.,割(cut):将容量网络中的发点和收点分割开,使s到t的流中断的一个弧集合.,割的容量:割的弧集合中各弧的容量之和,用 表示,显然,三.增广链（augmenting chain（path）:如果在网络的发点和收点之间能找出一条链,在这条链上所有的指向为st的弧(称为前向弧,记为 ),存在f0,这样的链称为增广链.,为加在弧上的负载, 是弧上的容量.,当有增广链时,找出,再令,显然 仍是一个可行流,与原来的可行流 比较发现,网络中从st的流量增大了一个 值( 0).,因此,只有当网络中找不到增广链时,st的流才不可能进一步增大.,四.求网络最大流的标号法,该算法是由Ford,Fulkerson于1956年提出,故称Ford-Fulkerson标号法.算法的实质是判断网络中是否存在增广链,并将其找出来.,算法步骤:,首先给发点s标号,记为 ,括号中第一个数字是使这个点得到标号的前一个点的代号,第二个数字表示从上一个标号点到这一标号点的流量的最大允许调整值;,找出与已标号点相邻的所有未标号点., 考虑从标号点i出发的弧(i,j),如有 不给j点标号;若有 则对j点标号,记为 其中i表示j点的标号是从i点延伸过来的, 考虑所有指向i的弧(h,i),如有 对h点不标号,若有 则对h点标号,记为, 如果某未标号点k有两个以上的相邻的标号点,为减少迭代次数,可按(1),(2)中的规则,分别计算 的值,取其中最大的一个标记., 重复步骤2,可能出现两种结局:, 标号过程中断,t点得不到标号,说明网络中不存在增广链,网络中给定的流就是最大流.计算结束;, t点得到标号,这时反向追踪,在网络中找到一条从s到t 的由标号点和相应的弧连结而成的增广链., 修改流量:设在网络中原有的流量为f., 抹去网络图中的所有标号,重复第1到第4步,一直到在网络中找不到任何增广链,即出现第3步的结局(1)为止,这时网络中的流量为网络的最大流.,例8 用标号法求下面网络从s到t的最大流量,并找出该网络的最小割.,解:,先给s标号 ;,从s点出发的弧为 ,因为 对 暂时不标