图与网络分析到最短路问题

《图与网络分析到最短路问题》由会员分享，可在线阅读，更多相关《图与网络分析到最短路问题（67页珍藏版）》请在金锄头文库上搜索。

1、第1页第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题第2页第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题第3页图论是应用非常广泛的运筹学分支，它 已经广泛地应用于物理学控制论，信息论， 工程技术，交通运输，经济管理，电子计算 机等各项领域。对于科学研究，市场和社会 生活中的许多问题，可以同图论的理论和方 法来加以解决。例如，各种通信线路的架设 ，输油管道的铺设，铁路或者公路交通网络 的合理布局等问题，都可以应用图论的方法 ，简便、快捷地加以解决。引 言第4页1736年

2、瑞士科学家欧拉发表了关于图论方面的第 一篇科学论文，解决了著名的哥尼斯堡七座桥问题。 即一个漫步者如何能够走过这七座桥，并且每座桥只 能走过一次，最终回到原出发地。如图1所示。引例1欧拉将这个问题抽象成一笔画问 题。即能否从某一点开始不重复 地一笔画出这个图形，最终回到 原点。欧拉在他的论文中证明了 这是不可能的，因为这个图形中 每一个顶点都与奇数条边相连接 ，不可能将它一笔画出，这就是 古典图论中的第一个著名问题。第5页在实际的生产和生活中，人们为了反映事物之间 的关系，常常在纸上用点和线来画出各式各样的示意 图。引例2左图是我国北京、上海、重庆等 十四个城市之间的铁路交通图， 这里用点表示

3、城市，用点与点之 间的线表示城市之间的铁路线。 诸如此类还有城市中的市政管道 图，民用航空线图等等。连云港武汉南京徐州上海北京塘沽青岛济南天津郑州第6页有六支球队进行足球比赛，我们分别用点 v1v6表示这六支球队，它们之间的比赛情况，也 可以用图反映出来，已知v1队战胜v2队，v2队战胜 v3队，v3队战胜v5队，如此等等。这个胜负情况， 可以用下图所示的有向图反映出来。引例3v3v1v2v4v6v5第7页图的基本概念与模型点：研究对象（车站、国家、球队）； 点间连线：对象之间的特定关系（陆地间有桥、铁 路线、两球队比赛及结果)。 对称关系：桥、道路、边界；用不带箭头的连线表 示，称为边。 非

4、对称关系：甲队胜乙队，用带箭头的连线表示， 称为弧。图：点及边（或弧）组成。注意：一般情况下，图中的相对位置如何，点与点之间线 的长短曲直，对于反映研究对象之间的关系，显的并不重 要，因此，图论中的图与几何图，工程图等本质上不同。第8页对 称 关 系非 对 称 关 系 无向图：图由点和边所构成的，记作G = = V ,E(V是点的集合，E是边的集合)连接点vi,vjV的边记作eij=vi,vj，或者vj,vi。 有向图：图是由点和弧所构成的，记作D=V ,A(V是点的集合，A是弧的集合) ， 一条方向从vi指向vj的弧，记作(vi,vj)。 图的相关概念网络图：给图中的点和边赋予具体的含义和权

5、数，如距离，费用，容量等，记作N.第9页图的相关概念若边eij=vi,vjE，称vi，vj是eij的端点，也称vi，vj 是相邻的。称eij是点vi（及点vj）的关联边。 若两条边有一个公共的端点，则称这两条边相邻。vivjevi，vj相邻 e 与vi，vj关联vie1vjvke2点与边关联点与点 相邻边与边相邻第10页若某条边两个端点相同，称这条边为环。若两点之间有多于一条的边，称这些边为多重边。 无环、无多重边的 图称为简单图。无环、但允许有多 重边的图称为多重 图。v1e1e2e3v2v3e5e4v4v5注：无特别声明我们今后讨论的图都是简单图图的相关概念第11页图G中以点v为端点的边的

6、数目，称为v在G中的 次(度）， 记为d（v）。d(v1)=2 d(v2)=3 d(v3)=4 d(v4)=1次为1 的点为悬挂点，悬挂点的关联边称为悬 挂边，次为零的点称为孤立点。v1e1e2e3v2v3e5e4v4v5次为奇数的点称为奇点，否则称为偶点。图的相关概念第12页给定图G=（V，E），若图G=（V，E），其中 VV，E E ，则称G是G的子图。 给定图G=（V，E），若图G=（V，E），其中EE ，则称G是G的一个支撑子图（部分图）。点全部保留（a）（b）子图（c）部分图子图与部分图（支撑子图）第13页图的连通性链：设图G=（V，E）中有一个点、边交替序 列 v1 ,e1,v2,

7、vn-1,en-1 ,vn，若 ei=(vi,vi+1)，即这(n-1)条边把n个顶点串 连起来，我们称这个交替序列为图G中的一 条链，而称点v1,vn为该链的两个端点。对于简单图链也可以仅用点的序列来表示。 如果一条链的两个端点是同一个点，则称它为闭链或圈； 如果一条链的各边均不相同，则称此链为简单链； 更若一条链的各点、各边均不相同，则称该链为初等链。v1v3v5e1e2 v7v8e7v2v4v6e3e4e5e6e8e9简单链：1=（v2，v1，v3，v6，v4，v3，v5）初等链：2=（v2，v1，v3，v5）第14页图的连通性最短链:网络中链上权值的和称为链的长度 ，以点v1,vn为端

8、点的诸链中长度最短的 链称为这两点的最短链。 连通图：如果图G=（V，E）中的任意两点都 是其某一条链的两个端点，则称图G是连 通图，否则，称图G是不连通的。 v1v3v5e1e2v7v8e7v2v4v6e3e4e5e6e8e9为不连通图， 有两个连通分 图组成第15页图的矩阵表示图的矩阵表示主要方法有：权矩阵、邻接矩阵。权矩阵网络图N=（V，E），边vi，vj的权为wij ，构造矩阵称矩阵A为网络N的权矩阵。v4v5v2v1v3234567894其权矩阵为： 注：当G为无向图时，权矩阵为对称矩阵。第17页图G=（V，E），p=n，构造矩阵称矩阵A为G的邻接矩阵。邻接矩阵？vi与vj不相邻图的

9、矩阵表示其邻接矩阵为： v4v5v2v1v3注：当G为无向图时，邻接矩阵为对称矩阵。思考：有甲、乙、丙、丁、戊、己六名运动员报名参加A 、B、C、D、E、F六个项目的比赛，下表中打的是个运动员报 名参加比赛的项目，问六个项目的比赛顺序应如何安排？做到 每名运动员都不连续地参加两项比赛。ABCDEF分析：点表示项目，边表示两个项目有同一名运动员参加 目的：在图中找出点序列 ，使得依次排列的两个点 不相邻，就找到了每名运 动员不连续参加两项比赛 的安排方案A、C、B、F、E、D (不唯一)第20页第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最

10、大流问题第21页第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题第22页7个村庄要在他们之间架设电话线，要求任何两个村庄都可 以互相通电话(允许中转)，并且电话线根数最少？引例村庄1村庄4村庄3村庄6村庄2村庄5村庄7分析：用七个点代表村庄，如果在某两个村庄之间架设电 话线，则相应的在两点之间连一条边，这样电话线网就可 以用一个图来表示，并且满足如下要求：连通图 图中有圈的话，从圈中任去掉一条边，余下的图仍连通第23页树村庄1村庄4村庄3村庄6村庄2村庄5村庄7如果G=（V，E）是一个无圈的连通图，则称G为树。 树中必存在次为1的点

11、（悬挂点） 树中任两点必有一条链且仅有一条链； 在树的两个不相邻的点之间添加一条边，就得到一个圈；反之，去掉树的任一条边，树就成为不连通图； n个顶点的树有（n-1）条边。树是最脆弱的连通图！第24页145241575237图的部分树（支撑树 ）如果图G=（V，E）的部分图G=（V，E）是树，则称G是G的部分树（或支撑树）。村庄1村庄4村庄3村庄6村庄2村庄5村庄7部分树上各树枝上权值的和称为它的长度，其中长度 最短的部分树，称其为该图的最小部分树（最小支撑 树）。点保留 边可去 仍是树 不唯一思考：如何铺设电话线，使得电话线长度最少？第25页ijkml最小部分树的求法定理：图中任一个点i，若

12、j是与相邻点中距离最近的， 则 边i,j一定必含在该图的最小部分树内。推论：把图的所有点分成 和 两个集合，则两集合之 间连线的最短边一定包含在最小部分树内。避圈法破圈法第26页227541435 1 75ABCDEST 算法的步骤：1、在给定的赋权的连通图上任选一点vi ,其余点在 中。2、从 与 的连线中找出权数最小的边vi, vj，这条边一 定包含在最小部分树内，做以标记。3、令 vj ， ；4、重复2、3两步，直至所有点都包含在 中为止。vj避圈算法S第27页77ABCDEST22541435 15破圈算法 算法的步骤：1、在给定的赋权的连通图上任找一个圈。2、在所找的圈中去掉一个权数

13、最大的边（如果有两条或 两条以上的边都是权数最大的边，则任意去掉其中一条 ）。3、如果所余下的图已不包含圈，则计算结束，所余下的 图即为最小生成树，否则返回第1步。第28页第六章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题第29页第八章 图与网络分析 图的基本概念与模型 树图和图的最小部分树 最短路问题 网络最大流问题 最小费用最大流问题第30页 什么是最短路问题？什么是最短路问题？ 固定起点的最短路Dijkstra(狄克斯拉) (荷兰)算法：标号法 每 对 顶 点 之 间 的 最 短 路矩阵算法最短路问题第31页最短路问题提出 在现

14、实生活中，除公路运输网络、电讯网 络等网络图以外，还有输油管线这样的图。在 输油管线图中，为反映油的输送情况，两点间 不仅有连线，线上往往还标有箭头，以表示油 的流动方向。又如，指挥系统图、控制系统图 等图中都标有指向。从这样的一类图中就可以 概括为有向图的概念。第32页有向图 由点集 和V 中元素的有序对的一个集合所组成的二元组称为有向图，记为D=（V，A）。其中V中的元素 vi叫做顶点，A中元素aij叫做以vi为始点（尾），vj为终点（ 首）的弧。 aij与aji作为具有不同指向的弧是不同的。第33页有向网络与混合图 如果在图D=（V，A）中，给每一弧赋予权值， 如将弧aij=(vi,vj

15、)有权值 wij，记为w(aij)=wij则 赋权有向图D=（V，A）称为有向网络，在不至 于混淆时，也简称网络。 混合图如果一个图中既有边，也有弧，那么称 这种图为混合图。它往往出现在既有单行线， 又有双行线的交通图中。1253 43 72第34页最短路问题引例下图为单行线交通网，每弧旁的数字表示通过这条线 所需的费用。现在某人要从v1出发，通过这个交通网 到v8去，求使总费用最小的旅行路线。v2v52 3464v3v1v4v6121061210v8v9v7236 3从v1到v8：P1=（v1，v2，v5，v8） 费用 6+1+6=13P2=（v1，v3，v4， v6， v7， v8） 费用 3+2+10+2+4=21P3= 从v1到v8的旅行路线 从v1到v8的路。旅行路线总费用 路上所有弧权之和。最短路问题中，不考虑有向环、并行弧。v2v52 3464v3v1v4v6121061210v8v9v7236 3第36页几个概念路：设p是D中一个首尾相连的弧的集合，如果vs是 它的第一条弧的始点，vt是它的最后一条弧的终 点，则称它是以点v