图与网络分析最短路(1)

1、. 第6章 图与网络分析 图的基本概念与基本定理 树和最小支撑树 最短路问题 网络最大流本章内容重点.引引 言言图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。.引引 言言随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决

2、许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。.引引 言言 1736年瑞士科学家欧拉发表了关于图论方面的第一篇科学论文，解决了著名的哥尼斯堡七座桥问题。德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，如图1a所示。.引引 言言AB图1 aCD.引引 言言 当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。 为了寻找答案，1736年欧拉将这个问题抽象成图1b所示图形的一笔画问题。即能否从某一点开始不重复地一笔画出这个图形，最终回到原

3、点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。.引引 言言图1 bACDB. 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。 例：公路或铁路交通图、管网图、通讯联络图等各节点及联系的边。如果用点表示研究的对象，用边表示这些对象之间的联系，则图G可以定义为点和边的集合G=V,E式中：V点的集合,E边的集合 如果给图中的点和边赋以具体的含义和权数，如距离、费用、容量等这样的图称为网络图。 1.1.图的基本概念与模型图的基本概念与模型. 用点和点之间的线所构成的图

4、，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图，工程图等本质上是不同的。.如图如图6-16-1所示：所示：端点，关联边，相邻环，多重边，简单图次，奇点，偶点，孤立点链，圈，路，回路，连通图完全图，偶图子图，部分图例1.2.2.树和最小支撑树树和最小支撑树树图（简称树，记作T（V,E） 在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。 .性质1 任何树中必存在次为1的点

5、。性质2 具有n个顶点的树的边数恰好为 （n-1）条。性质3 任何具有n个点、（n-1）条边的连通 图是树图。2.1树的性质.2.2 2.2 图的最小部分树图的最小部分树v如果G1是G2的部分图，则称G1是G2的部分树（或支撑树）。树图的各条边称为树枝（假定各边均有权重），一般图G2含有多个部分树，其中树枝总长最小的部分树，称为该图的最小部分树（也称最小支撑树）v定理1 图中任一个点i，若j是与i相邻点中距离最近的，则边i,j一定必含在该图的最小部分树内。v推论 把图的所有点分成V和 两个集合，则两集合之间连线的最短边一定含在最小部分树内。V.练习:写下图的树图v6v5v2v3v4v1v6v5

6、v2v3v4v1.练习练习v用破圈法求出下图的一个树图。V V5 5V V4 4V V2 2V V3 3V V1 1e e6 6e e5 5e e4 4e e3 3e e2 2e e1 1e e7 7e e8 8. 取一个圈(v1,v2,v3,v1)，在一个圈中去 掉边e3 。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4 。再从圈（v3,v4 v5,v3）中去掉边e6 。再从圈 (v1,v2,v5,v4,v3,v1 ）中去掉边e7， 这样，剩下的图不含圈，于是得到一个 支撑树，如下图所示。v v2 2e e1 1e e2 2e e5 5e e8 8v v1 1v v3

7、3v v4 4.2.3 避圈法和破圈法（1）避圈法v 从网络图中依次寻找权数较小的边，寻找过程中，节点不得重复，即不得构成圈。注意在找较小权数边时不考虑已选过的边和可能造成圈的边。如此反复进行，直到得到最短树或证明网络不存在最短树。v在图中寻找最小部分树的步骤：P153.（2）破圈法 在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树； 去掉该圈中权数最大的边； 反复重复 两步，直到最短树。.练习：用破圈法求出下图的最小部分树图av6v5v2v3v4v1627535441v3v2v1v4v6v553142图b.最短路问题最短路问题是网络理论中应用最广泛的问题之一。许多优化问题

8、都可以使用这个模型，如设备更新、管道的铺设、线路的安排、厂区的布局等。最短路问题的一般提法是：设为连通图，图中各边有权(表示，之间没有边）,为图中任意两点，求一条道路，使它是从到的所有路中总权最小的路。即：),(EVG ),(jivvijlijliv,svjvtvsvtv),()(jivvijlL最小。.最短路算法中1959年由（狄克斯特洛）提出的算法被公认为是目前最好的方法，我们称之为算法。下面通过例子来说明此法的基本思想。DijkstraDijkstra条件：所有的权数0ijl思路：逐步探寻。1v2v3v5v7v8v6v4v4676151955447.1v2v3v5v7v8v6v4v467

9、6151955447下求到的最短路：1v8v1）从出发，向走。首先，从到的距离为0，给标号（0）。画第一个弧。（表明已标号，或已走出）1v8v1v1v1v1v1v)0(从出发，只有两条路可走，其距离为1v),(21vv),(31vv2）,412l.613l.1v2v3v5v7v8v6v4v4676151955447)0(可能最短路为46 , 4min,min,min13121312llkk),(21vv2v)4(给划成粗线。 划第二个弧。给标号（4）。.1v2v3v5v7v8v6v4v4676151955447)0()4(表明走出后走向的最短路目前看是，最优距离是4。1v8v),(21vv现已

10、考察完毕第二个圈内的路，或者说，已完成的标号。,1v2v.1v2v3v5v7v8v6v4v4676151955447)0()4(3）接着往下考察，有三条路可走：),(42vv),(31vv).,(52vv可选择的最短路为644 , 54 , 6min,min,min2512241213252413dldllkkk),(31vv3v)6(给划成粗线。 划第3个弧。给标号（6）。.1v2v3v5v7v8v6v4676151955447)0()4()6(4）接着往下考察，有四条路可走：),(42vv).,(52vv可选择的最短路为813,10, 8 , 9min,min35342524kkkk5v4

11、v),(43vv).,(53vv),(52vv)8(给划成粗线。 划第4个弧。给标号（8）。.1v2v3v5v7v8v6v4676151955447)0()4()6(5）接着往下考察，有四条路可走：),(42vv可选择的最短路为914,13,10, 9min,min57563424kkkk4v),(43vv),(65vv),(42vv)8().,(75vv4v)9(给划成粗线。 划第5个弧。给标号（9）。.1v2v3v5v7v8v6v4676151955447)0()4()6(6）接着往下考察，有四条路可走：),(64vv可选择的最短路为1314,13,16,18min,min57564746

12、kkkk6v),(74vv),(65vv),(65vv)8().,(75vv4v)9()13(给划成粗线。 划第6个弧。给标号（13）。.1v2v3v5v7v8v6v4676151955447)0()4()6(7）接着往下考察，有四条路可走：可选择的最短路为1414,18,14,16min,min68675747kkkk8v),(76vv),(75vv)8(),(75vv4v)9()13().,(86vv)14(),(74vv),(86vv,7v)14(同时给划成粗线。分别给标号（14）。.最后，从逆寻粗线到，得最短路：1v2v3v5v7v8v6v4676151955447)0()4()6()

13、8(4v)9()13()14()14(8v1v86521vvvvv长度为14。.最短路问题的两个应用最短路问题在图论应用中处于很重要的地位，下面举两个实际应用的例子。例1设备更新问题某工厂使用一台设备，每年年初工厂要作出决定：继续使用，购买新的？如果继续使用旧的，要负维修费；若要购买一套新的，要负购买费。试确定一个5年计划，使总支出最小若已知设备在各年的购买费，及不同机器役龄时的残值与维修费，如表2所示.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表2解：把这个问题化为最短路问题。用点表示第i年初购进一台新

14、设备，虚设一个点，表示第5年底。6viv边表示第i年购进的设备一直使用到第j年初（即第j-1年底）。),(jivv.边上的数字表示第i年初购进设备，一直使用到第j年初所需支付的购买费、维修的全部费用（可由表8-2计算得到）。),(jivv1v2v3v4v5v6v131219284059151520294122213014这样设备更新问题就变为：求从到的最短路问题.1v6v.项目第1年第2年第3年第4年第5年购买费1112131414机器役龄0-11-22-33-44-5维修费5681118残值43210表21v2v3v4v5v6v131219284059151520294122213014.)

15、12(2v3v4v5v6v131219284059151520294122213014 1v)0( 1259,40,28,19, ,12min,min1615141312kkkkk1v)0(),(21vv给划成彩线。194112,2912,2012,1312,59,40,28,19min,min2625242316151413kkkkkkkk.)12(2v)19(3v)28(4v5v6v1312192840591515202941222130141v)0(),(31vv给划成彩线。2849,40,33,53,41,32,59,40,28min,min363534262524161514kkkk

16、kkkkk),(41vv给划成彩线。.1516252635364546min,min40,59,41,43,40,49,43,5040kkkkkkkk)12(2v)19(3v)28(4v)40(5v6v1312192840591515202941222130141v)0(),(51vv给、划成彩线。35(,)v v.)12(2v)19(3v)28(4v)40(5v6v1312192840591515202941222130141v)0(4955,50,49,53,59min,min5646362616kkkkk),(63vv给划成彩线。计算结果：最短路631vvv.)12(2v)19(3v)2

17、8(4v)40(5v6v13192840591515202941222130141v)0(12最短路路长为49。即：在第一年、第三年初各购买一台新设备为最优决策。这时5年的总费用为49。.例3(选址问题)已知某地区的交通网络如图所示，其中点代表居民小区，边代表公路，边权为小区间公路距离，问区中心医院应建在哪个小区，可使离医院最远的小区居民就诊时所走的路程最近？1v6v3v2v4v5v7v301520301520256018解求中心的问题。解决方法：先求出到其它各点的最短路长如ivjd1123737( )max ,max0,30,D vd d dddd再求.)(,),(),(min721vDvD

18、vD即为所求。1v)18(6v2v7v30152030152025185v60)0(4v比如求)(4vD 4v)0( 1818,30,20min,min464543kkk),(64vv给划成彩线。3v.1v)18(6v2v7v30152030152025185v60)0(4v)20(3v2033,33,43,30,20min,min6762634543kkkkk),(34vv给划成彩线。给标号20。3v.1v)18(6v)33(2v7v3015203015202518)30(5v60)0(4v)20(3v3033,33,40,80,30min,min6762323545kkkkk),(54vv

19、给划成彩线。给标号30。5v.1v)18(6v)33(2v3015203015202518)30(5v60)0(4v)20(3v3333,33,40min,min676232kkk),(26vv分别给划成彩线。分别给标号33。72,vv)33(7v),(76vv.)60(1v)18(6v1v3015203015202518)30(5v60)0(4v)20(3v6363minmin21k给划成彩线。给标号63。),(12vv)33(7v)33(2v其它计算结果见下表：. 小区号0 30 50 63 93 45 609330 0 20 33 63 15 306350 20 0 20 50 25 4

20、05063 33 20 0 30 18 336393 63 50 30 0 48 639345 15 25 18 48 0 154860 30 40 33 63 15 063表11v1v3v3v2v2v4v4v5v5v6v6v7v7v)(ivD由于最小，所以医院应建在，此时离医院最远的小区距离为48。48)(6vD6v5v.第四节最大流问题最大流问题是一类应用极为广泛的问题，例如在交通运输网络中有人流、车流、货物流、供水系统中有水流，金融系统中有现金流，通信系统中有信息流，等等。一有关概念：例：下图是输油管道网，为起点，为终点，为中转站，边上的数字表示该管道的最大输油能力（也称容量），记为，问

21、应如何安排各管道输油量，才能使从到的总输油量最大？1v3v2v,4v,5vsvtv6vijc.1v3v2v4v5vsvtv6v22333455534 分别称为发点、收点。其余的点称为中间点。,svtv每一个边上都给定一个容量的网络称为容量网络，记),(CEVG 的每一个边上都给定一个实际流量的网络称为给 定了网络一个流。Gijf.1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(容量限制条件：对每一边上都有ijijcf0平衡条件：a)中间点：流入量=流出量。b

22、)发收点：发出流量=汇入流量。若，称边是饱和边。ijijcf),(ijijfc.可增广链：是指从到有一条链，此链上有的现象出现。（非饱和链）svtvijfijc这种流称为可行流。上图就是一个可行流。使流量达到最大的流称为最大流。二求解最大流： 先给标号（，+），其中意思是流入的结点，现没 有，纯属一个符号。+表示的流出量。因它上面没有结点 来控制它，故设为+.1）寻找可增广链：sv.b)接着检查与相邻接的点，。已饱和，流量不可再增。再检查，可调整量为4-2=2，可提供量+，取调整量1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5

23、()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),(1v2v3v1v2v2, 24min2v.给标号，其中表示的所调整量2来自，且为正向流（向前流）。1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2()2 ,(sv),(sv2vsv同理，给标号3v) 1,(sv 下对已标号点（可望调整点）接着向下检查。已饱 和。再检查与相邻接且未标号的点6v2v,5v6v2v)2 ,(sv) 1 ,(sv.调整量为1v3v2v4v5vsvtv6v)5

24、 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv22, 03min5v给标号为5v)2 ,(2v)2 ,(2vd)检查与相邻接且未标号的点，。而对来讲是流入，现欲增加流出量，应压缩的流入量，只要的流入量5v1vtv1v5v1v.1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(2v, 015f可令调整量为22, 3min1v给标号为)2 ,(5v1v)2 ,(5v表示可控量，反方向流量。.1v3v2v4v5vsvtv6v)5 , 5()2 , 3()2 , 4()2 , 5()2 , 4()4 , 5()3 , 3()3 , 3()0 , 3()2 , 2()2 , 2(),()2 ,(sv) 1 ,(sv)2 ,(