《图与网络分析到最短路问题.ppt》由会员分享，可在线阅读，更多相关《图与网络分析到最短路问题.ppt（87页珍藏版）》请在三一文库上搜索。
1、第八章 图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,第八章 图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。,引 言,1736年瑞士科学家欧拉发表了关于图论方面
2、的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。即一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。如图1所示。,引例1,欧拉将这个问题抽象成一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。,在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。,引例2,左图是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸如此类还有
3、城市中的市政管道图，民用航空线图等等。,有六支球队进行足球比赛，我们分别用点v1v6表示这六支球队，它们之间的比赛情况，也可以用图反映出来，已知v1队战胜v2队，v2队战胜v3队，v3队战胜v5队，如此等等。这个胜负情况，可以用下图所示的有向图反映出来。,引例3,图的基本概念与模型,点：研究对象（车站、国家、球队）；,点间连线：对象之间的特定关系（陆地间有桥、铁路线、两球队比赛及结果)。,对称关系：桥、道路、边界；用不带箭头的连线表 示，称为边。,非对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。,图：点及边（或弧）组成。,注意：一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于
4、反映研究对象之间的关系，显的并不重要，因此，图论中的图与几何图，工程图等本质上不同。,对 称 关 系,非 对 称 关 系,无向图：图由点和边所构成的， 记作G = V ,E(V是点的集合，E是边的集合) 连接点vi,vjV的边记作eij=vi,vj，或者vj,vi。 有向图：图是由点和弧所构成的， 记作D=V ,A(V是点的集合，A是弧的集合) ， 一条方向从vi指向vj的弧，记作(vi,vj)。,图的相关概念,网络图：给图中的点和边赋予具体的含义和权数，如距离， 费用，容量等，记作N.,图的相关概念,若边eij=vi,vjE，称vi，vj是eij的端点，也称vi，vj是相邻的。称eij是点v
5、i（及点vj）的关联边。,若两条边有一个公共的端点，则称这两条边相邻。,点与边关联,点与点相邻,边与边相邻,若某条边两个端点相同，称这条边为环。 若两点之间有多于一条的边，称这些边为多重边。,无环、无多重边的图称为简单图。,无环、但允许有多重边的图称为多重图。,注：无特别声明我们今后讨论的图都是简单图,图的相关概念,图G中以点v为端点的边的数目，称为v在G中的次(度）， 记为d（v）。,d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1,次为1 的点为悬挂点，悬挂点的关联边称为悬挂边，次为零的点称为孤立点。,次为奇数的点称为奇点，否则称为偶点。,图的相关概念,给定图G=（V，E），
6、若图G=（V，E），其中VV，E E ，则称G是G的子图。,给定图G=（V，E），若图G=（V，E），其中EE，则称G是G的一个支撑子图（部分图）。,点全部保留,部分图,子图与部分图（支撑子图）,图的连通性,链：设图G=（V，E）中有一个点、边交替序列 v1 ,e1,v2,vn-1,en-1 ,vn，若ei=(vi,vi+1)，即这(n-1)条边把n个顶点串连起来，我们称这个交替序列为图G中的一条链，而称点v1,vn为该链的两个端点。,对于简单图链也可以仅用点的序列来表示。 如果一条链的两个端点是同一个点，则称它为闭链或圈； 如果一条链的各边均不相同，则称此链为简单链； 更若一条链的各点、各边
7、均不相同，则称该链为初等链。,图的连通性,最短链:网络中链上权值的和称为链的长度，以点v1,vn为端点的诸链中长度最短的链称为这两点的最短链。 连通图：如果图G=（V，E）中的任意两点都是其某一条链的两个端点，则称图G是连通图，否则，称图G是不连通的。,为不连通图，有两个连通分图组成,图的矩阵表示,图的矩阵表示主要方法有：权矩阵、邻接矩阵。,权矩阵 网络图N=（V，E），边vi，vj的权为wij ，构造矩阵,称矩阵A为网络N的权矩阵。,其权矩阵为：,注：当G为无向图时，权矩阵为对称矩阵。,图G=（V，E），p=n，构造矩阵,称矩阵A为G的邻接矩阵。,邻接矩阵,？,vi与vj不相邻,图的矩阵表示
8、,其邻接矩阵为：,注：当G为无向图时，邻接矩阵为对称矩阵。,思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到每名运动员都不连续地参加两项比赛。,A,B,C,D,E,F,分析：点表示项目，边表示两个项目有同一名运动员参加,目的：在图中找出点序列，使得依次排列的两个点不相邻，就找到了每名运动员不连续参加两项比赛的安排方案,A、C、B、F、E、D,(不唯一),第八章 图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,第八章 图与网络分
9、析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,7个村庄要在他们之间架设电话线，要求任何两个村庄都可以互相通电话(允许中转)，并且电话线根数最少？,引例,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,分析：用七个点代表村庄，如果在某两个村庄之间架设电话线，则相应的在两点之间连一条边，这样电话线网就可以用一个图来表示，并且满足如下要求：,连通图 图中有圈的话，从圈中任去掉一条边，余下的图仍连通,为什么？,树,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,如果G=（V，E）是一个无圈的连通图，则称G为树。,树中必存在次为1的点（悬挂
10、点） 树中任两点必有一条链且仅有一条链； 在树的两个不相邻的点之间添加一条边，就得到一个圈； 反之，去掉树的任一条边，树就成为不连通图； n个顶点的树有（n-1）条边。,树是无圈连通图中边数最多的，也是最脆弱的连通图！,图的部分树（支撑树）,如果图G=（V，E）的部分图G=（V，E）是树， 则称G是G的部分树（或支撑树）。,村庄1,村庄4,村庄3,村庄6,村庄2,村庄5,村庄7,部分树上各树枝上权值的和称为它的长度，其中长度最短的部分树，称其为该图的最小部分树（最小支撑树）。,点保留 边可去 仍是树 不唯一,思考：如何铺设电话线，使得电话线长度最少？,最小部分树的求法,定理：图中任一个点i，若
11、j是与相邻点中距离最近的， 则边i,j一定必含在该图的最小部分树内。,推论：把图的所有点分成 和 两个集合，则两集合之间连线的最短边一定包含在最小部分树内。,避圈法,破圈法,2,2,7,5,4,1,4,3,5,1,7,5,求解最小生成树的避圈算法,S,A,B,C,D,E,S,T,2,2,1,3,1,5,求解最小生成树的破圈算法,算法的步骤： 1、在给定的赋权的连通图上任找一个圈。 2、在所找的圈中去掉一个权数最大的边（如果有两条或两条以上的边都是权数最大的边，则任意去掉其中一条）。 3、如果所余下的图已不包含圈，则计算结束，所余下的图即为最小生成树，否则返回第1步。,第八章 图与网络分析,图的
12、基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,第八章 图与网络分析,图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题,什么是最短路问题？ 固定起点的最短路 Dijkstra(狄克斯拉) (荷兰)算法：标号法 逐次逼近算法(Ford(美国)算法)：修正标号法 每 对 顶 点 之 间 的 最 短 路 路矩阵算法(Floyd(佛洛伊德)算法),最短路问题,最短路问题提出,在现实生活中，除公路运输网络、电讯网络等网络图以外，还有输油管线这样的图。在输油管线图中，为反映油的输送情况，两点间不仅有连线，线上往往还标有箭头，以表
13、示油的流动方向。又如，指挥系统图、控制系统图等图中都标有指向。从这样的一类图中就可以概括为有向图的概念。,有向图,由点集 和V 中元素的有序对的一个集合 所组成的二元组称为有向图，记为D=（V，A）。 其中 V中的元素 vi叫做顶点， A中元素aij叫做以vi为始点（尾），vj为终点（首）的弧。 aij与aji作为具有不同指向的弧是不同的。,有向网络与混合图,如果在图D=（V，A）中，给每一弧赋予权值，如 将弧aij=(vi,vj)有权值 wij，记为w(aij)=wij则赋权有向图D=（V，A）称为有向网络，在不至于混淆时，也简称网络。 混合图如果一个图中既有边，也有弧，那么称这种图为混合图
14、。它往往出现在既有单行线，又有双行线的交通图中。,最短路问题引例,下图为单行线交通网，每弧旁的数字表示通过这条线所需的费用。现在某人要从v1出发，通过这个交通网到v8去，求使总费用最小的旅行路线。,从v1到v8： P1=（v1，v2，v5，v8） 费用 6+1+6=13 P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21 P3= ,最短路问题中，不考虑有向环、并行弧。,几个概念,路：设p是D中一个首尾相连的弧的集合，如果vs是它的第一条弧的始点，vt是它的最后一条弧的终点，则称它是以点vs为始点，以点vt为终点的一条路。 路长：路p中所有弧的权值的和称为路p的
15、长，记为,设图D=（V，A）是一有向网络,设P是以点vs为始点，以点vt为终点的所有路的集合， 如果 ,且 ，则称p0是以点vs 为始点，以点vt为终点的最短路。而称其路长为点 vi到点vj的距离，记为 。,几个概念,最短路及一点到另一点的距离,最短路问题是重要的最优化问题之一，可以直接应用于解 决生产实际的许多问题:管道铺设、线路安排、厂区布局等。 而且经常被作为一个基本工具来解决其他的优化问题。,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,求解最短路问题的Dijkstra算法,条件：当所有 wij
16、0 时，用来求给定点vs到任一 个点vj 最短路的公认的最好方法。,事实：如果P是D中从vs到vj的最短路，vi是P中的一 基解 个点，那么，从vs沿P到vi的路是从vs到vi的最基解 短路。,Dijkstra算法是Dijkstra在1959年提出的，可用于求解指定两点间的最短路问题，或从指定点到其余各点的最短路问题。由于其以标号为主要特征，又称为标号法。,v5,最短路的子路是最短路,Dijkstra算法基本思想,从始点vs出发，逐步顺序地向外探寻，每向外延伸一步都要求是最短的。执行过程中，与每个点对应，记录下一个数(称为这个点的标号),1.标号 P（固定标号或永久性标号） 从始点vs到该标号
17、点vj的最短路权P (vj) 。 2.标号 T（临时性标号） 从始点vs到该标号点vj的最短路权上界T (vj) 。,j ,P (vj),j, T (vj),该方法的每一步就是去修改T标号，并且把某一个具T标号的点 改变为具有P标号的点，从而使D中具P标号的顶点数多一个， 至多经过n-1步，就可以求出始点vs到各点的最短路。,前点标号j 表示始点vs到vj的最短路上vj的前一点。,Dijkstra算法步骤：,第二步：考虑满足条件 的所有点； vi具有P 标号;vj具有T 标号; 修改vj的T标号为 ， 并将结果仍记为T(vj),第一步：始点标上固定标号 ,其余各点标临时性标号 T(vj)=,
18、j1;,第三步：若网络图中已无T标号点，停止计算。 否则, 令 ，s为T标号点集, 然后将 的T 标号改成P 标号 ，转入第二步。,v1,6,图上标号法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,v1,1,v1,1,永久标号,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,v1,6,图上标号法,0,0,M, ,M, ,v1,3,M, ,M, ,M, ,0,0,v1,1,v4,11,v1,3,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v1,1,M, ,M,M, ,1,3,图上标号法,v4,11,v1,3,v1,6,v3,5,v3,
19、5,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v4,11,v1,1,M, ,M, ,M, ,v1,3,图上标号法,v3,5,v2, 6,v2, 6,永久标号,临时标号,v1出发到v8去，使总费用最小的旅行路线,0,0,M, ,v4,11,v1,1,M, ,M, ,v1,3,v5,12,v5,9,v5,9,图上标号法,v3,5,v2, 6,永久标号,临时标号,v5,10,v1出发到v8去，使总费用最小的旅行路线,0,0,v5,10,v1,1,M, ,v5, 12,v1,3,v5,9,v5, 12,v3,5,v2, 6,图上标号法,永久标号,临时标号,v5,10
20、,v1出发到v8去，使总费用最小的旅行路线,0,0,v5,10,v1,1,M, ,v1,3,v5, 12,v3,5,v2, 6,图上标号法,v5,9,永久标号,临时标号,标号结束 反向追踪,v1出发到v8去，使总费用最小的旅行路线,Dijkstra算法步骤：,第二步：考虑满足条件 的所有点； vi具有P 标号;vj具有T 标号; 修改vj的T标号为 ， 并将结果仍记为T(vj),第一步：始点标上固定标号 ,其余各点标临时性标号 T(vj)=, j1;,第三步：若网络图中已无T标号点，停止计算。 否则, 令 ，s为T标号点集, 然后将 的T 标号改成P 标号 ，转入第二步。,例 求如下交通网络中
21、v1 到各点间最短路路长。,Dijkstra算法（标号法）算例,混合图,无向网络:,负权弧时。,无向网络中，最短路最短链。,多个点对之间最短路？,Dijkstra算法失效,Dijkstra算法注意的问题,逐步逼近算法,路矩阵算法,5,7,2,7,4,6,1,2,6,3,2,0,2,6,5,7,7,10,v3,v1,v2,v4,v5,v6,v7,练习：求如下无向网络中v1到v7的最短链,Dijkstra算法求最短链,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,逐次逼近算法思想,该公式表明， P(1)1j中
22、的第j个分量等于P(0)1j的分量与基本表(权矩阵)中的第j列相应元素路长的最小值，它相当于在v1与vj之间插入一个转接点(v1,v2,vn中的任一个，含点v1与vj)后所有可能路中的最短路的路长；每迭代一次，就相当与增加一个转接点，而P(k)1j中的每一个分量则随着k的增加而呈不增的趋势！,用于计算带有负权弧指定点v1到其余各点的最短路,逐次逼近算法基本步骤,例 计算从点v1到所有其它顶点的最短路,解：初始条件为,以后按照公式 进行迭代。,直到得到 ，迭代停止。,4 0,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,4 0
23、,0 -1,6 0 2,4 0 -3 3,-3 0 7,5 -2 0 4,2 0,0,利用下标追踪路径,空格为无穷大,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,最短路问题求解方法,Dijkstra算法 逐步逼近算法 路矩阵算法,某些问题需要求网络上任意两点间的最短路。当然，它也可以用标号算法依次改变始点的办法来计算，但是比较麻烦。 这里介绍Floyd在1962年提出的路矩阵法，它可直接求出网络中任意两点间的最短路。,Floyd算法(路矩阵法)思想,考虑D中任意两点vi，vj，如将D中vi，vj以外的点都删掉，得只剩vi，vj的一个子网络D0，记,wij为弧（ vi，v
24、j）的权。,在D0中加入v1及D中与vi，vj，v1相关联的弧，得D1，D1中vi到vj的最短路记为 ,则一定有,Floyd算法(路矩阵法)思想,再在D1中加入v2及D中与vi，vj，v1， v2相关联的弧，得D2，D2中vi到vj的最短路长记为 ，则有,Floyd算法(路矩阵法)思想,Floyd算法(路矩阵法)步骤,设有有向网络D=（V，A），其权矩阵为A=(aij)nn，,如下构造路矩阵序列：,则n阶路矩阵D(n)中的元素d(n)ij就是vi到vj的最短路的路长。,令权矩阵A为初始路矩阵D（0），即令D（0）=A,2. 依次计算K阶路矩阵D（K）=（d(k)ij）nn, k=1,2,n，,
25、这里,路矩阵序列的含义,K阶路矩阵D（K） 其中的元素表示相应两点间可能以点v1、v2、vk为 转接点的所有路中路长最短的路的路长。,D（0） 其中的任一元素表示相应两点间无转接点时最短路路长。,一阶路矩阵D（1） 其中的元素表示相应两点间可能以点v1为转接点的所有路中路长最短的路的路长；,为使计算程序化，转接点按顶点下标的顺序依次加入,n阶路矩阵D(n) 其中的元素d(n)ij就是vi到vj的可能以点v1、v2、vn为转接点的所有路中路长最短的路的路长。既是vi到vj的最短路的路长。,例 求如下交通网络中各对点间最短路路长。,该图的权矩阵为：,Floyd算法(路矩阵法)算例,例 求如下交通网
26、络中各对点间最短路路长。,Floyd算法(路矩阵法)算例,利用公式,发现第一行，第一列元素不变,利用公式,发现第二行，第二列元素不变,利用公式,发现第三行，第三列元素不变,利用公式,发现第四行，第四列元素不变,D(5)中的元素给出相应两点间 的最短路，其下标给出最短路 个顶点下标,比如：,6254,已知有7个村子，相互间道路的距离如下图示。拟合建一所小学，已知A处有小学生30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人,问小学应建在哪一个村子，使学生上学最方便（原则所有人走的总路程最短；尽可能公平。）。,最短路问题算例1(选址问题),最短路问题算例1(选址问题)
27、,最短路问题算例1(选址问题),A处30人，B处40人，C处25人，D处20人，E处50人，F处60人， G处60人.,0 200 50 140 350 360 600,150 0 175 40 250 240 480,60 280 0 120 250 240 480,210 80 150 0 150 120 360,210 200 125 60 0 60 180,180 160 100 40 50 0 240,300 320 200 120 250 240 0,1700 1335 1430 1070 835 770 1330,A B C D E F G,A B C D E F G,某工厂使用
28、一台设备，每年年初工厂都要作出决定：如果继续使用旧的，要付维修费；如果买新的，要付购置费。试制定一个五年更新计划，使工厂总支出最少？,若该设备在各年的购置费、不同役龄的残值及维修费如下表：,最短路问题算例2(设备更新问题),最短路问题算例2(设备更新问题),弧（vi，vj）的权: 表示第i年初购买的设备一直使用到第j年年初所需支付的总费用，即第i年初的购置费加上第一年、第二年、第（j-i）年的维修费，再减去（j-i）年役龄残值。,解：为将该问题化为最短路问题，用点vi表示第i年初购买一台新设备，并虚设点v6表示第五年年底。,弧（vi，vj）：表示第i年初购买的设备一直使用到第j年年初（即第j-1年年底）；,这样一来，设备更新问题可归结为如下基本表中的求v1到v6的最短路问题。,用逐次逼近法较为简便,答：第一年初购买一台新设备一直用到第三年年初处理，再购买一台新设备一直用到第五年底可使支付的总费用最少。,