第八章图与网络分析PPT讲稿.ppt

第八章图与网络分析1第1页，共146页，编辑于2022年，星期三8.1 图的基本概念与基本定理图的基本概念与基本定理 图图论论是是应应用用非非常常广广泛泛的的运运筹筹学学分分支支，它它已已经经广广泛泛地地应应用用于于物物理理学学控控制制论论，信信息息论论，工工程程技技术术，交交通通运运输输，经经济济管管理理，电电子子计计算算机机等等各各项项领领域域。对对于于科科学学研研究究，市市场场和和社社会会生生活活中中的的许许多多问问题题，可可以以同同图图论论的的理理论论和和方方法法来来加加以以解解决决。例例如如，各各种种通通信信线线路路的的架架设设，输输油油管管道道的的铺铺设设，铁铁路路或或者者公公路路交交通通网网络络的的合合理理布布局局等等问问题题，都都可可以以应应用用图图论论的的方方法法，简简便便、快快捷捷地地加加以解决。以解决。第2页，共146页，编辑于2022年，星期三 随着科学技术的进步，特别是电子计算机技随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。工程技术人员和经营管理人员的重视。关于图的第一篇论文是瑞士数学家欧拉关于图的第一篇论文是瑞士数学家欧拉（E.Euler）在）在1736年发表的解决年发表的解决“哥尼哥尼第3页，共146页，编辑于2022年，星期三斯堡斯堡”七桥难题的论文；七桥难题的论文；德国的哥尼斯堡城有一条普雷格尔河，河中有德国的哥尼斯堡城有一条普雷格尔河，河中有两个岛屿，河的两岸和岛屿之间有七座桥相互连接，两个岛屿，河的两岸和岛屿之间有七座桥相互连接，（见图（见图8.1 a8.1 a）当地的居民热衷于这样一个问题，当地的居民热衷于这样一个问题，一个漫步者如何能够走过这七座桥，并且每座一个漫步者如何能够走过这七座桥，并且每座桥只能走过一次，最终回到原出发地。尽管试桥只能走过一次，最终回到原出发地。尽管试验者很多，但是都没有成功。为了寻找答案，验者很多，但是都没有成功。为了寻找答案，1736年欧拉将这个问题抽象成图年欧拉将这个问题抽象成图8.1b所示图形所示图形的一笔画问题。的一笔画问题。第4页，共146页，编辑于2022年，星期三哥尼斯堡七桥问题哥尼斯堡七桥问题图图 8.1 a 8.1 aA AB BC CD D第5页，共146页，编辑于2022年，星期三哥尼斯堡七桥问题可简化为以下图形哥尼斯堡七桥问题可简化为以下图形其中的四个顶点都是奇顶点其中的四个顶点都是奇顶点A AB BC CD D第6页，共146页，编辑于2022年，星期三C CA AD DB B图图8.1 b8.1 b第7页，共146页，编辑于2022年，星期三即能否从某一点开始不重复地一笔画出这个图形，即能否从某一点开始不重复地一笔画出这个图形，最终回到原点。欧拉在他的论文中证明了这是不可最终回到原点。欧拉在他的论文中证明了这是不可能的，因为这个图形中每一个顶点都与奇数条边相能的，因为这个图形中每一个顶点都与奇数条边相连接，不可能将它一笔画出，这就是古典图论中的连接，不可能将它一笔画出，这就是古典图论中的第一个著名问题。第一个著名问题。在实际的生产和生活中，人们为了反映事物在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样之间的关系，常常在纸上用点和线来画出各式各样的示意图。的示意图。第8页，共146页，编辑于2022年，星期三例例8.18.1 图图8.28.2是我国北京、上海、重庆等十四是我国北京、上海、重庆等十四个城市之间的铁路交通图，这里用点表示城市，个城市之间的铁路交通图，这里用点表示城市，用点与点之间的线表示城市之间的铁路线。诸用点与点之间的线表示城市之间的铁路线。诸如此类还有城市中的市政管道图，民用航空线如此类还有城市中的市政管道图，民用航空线图等等。图等等。石家庄石家庄太原太原北京北京天津天津塘沽塘沽济南济南青岛青岛徐州徐州连云港连云港南京南京上海上海郑州郑州武汉武汉重庆重庆图图8.28.2第9页，共146页，编辑于2022年，星期三 例例8.28.2 有六支球队进行足球比赛，我有六支球队进行足球比赛，我们分别用点们分别用点v1，v6表示这六支球队，它表示这六支球队，它们之间的比赛情况，也可以用图反映出来，们之间的比赛情况，也可以用图反映出来，已知已知v1 1队战胜队战胜v2 2 队，队，v2 队战胜队战胜v3 3 队，队，v3 3 队队战胜战胜v5队，如此等等。这个胜负情况，可以队，如此等等。这个胜负情况，可以用图用图8.38.3所示的有向图反映出来所示的有向图反映出来第10页，共146页，编辑于2022年，星期三图图8.38.3v3v5v2v4v6v1第11页，共146页，编辑于2022年，星期三 从从以以上上的的几几个个例例子子可可以以看看出出，我我们们用用点点和和点点之之间间的的线线所所构构成成的的图图，反反映映实实际际生生产产和和生生活活中中的的某某些些特特定定对对象象之之间间的的特特定定关关系系。一一般般来来说说，通通常常用用点点表表示示研研究究对对象象，用用点点与与点点之之间间的的线线表表示示研研究究对对象象之之间间的的特特定定关关系系。由由于于在在一一般般情情况况下下，图图中中的的相相对对位位置置如如何何，点点与与点点之之间间线线的的长长短短曲曲直直，对对于于反反映映研研究究对对象象之之间间的的关关系系，显显的的并并不不重重要要，因因此此，图图论论中中的的图图与与几几何何图图，工工程程图等本质上是不同的。图等本质上是不同的。第12页，共146页，编辑于2022年，星期三 综综上上所所述述，图图论论中中的的图图是是由由点点和和点点与与点点之之间间的的线线所所组组成成的的。通通常常，我我们们把把点点与与点点之之间间不不带带箭箭头头的的线线叫叫做做边边，带箭头的线叫做，带箭头的线叫做弧弧。如如果果一一个个图图是是由由点点和和边边所所构构成成的的，那那么么，称称为为无无向向图图，记记作作G=(V，E)，其其中中V表表示示图图G 的的点点集集合合，E表表示示图图G的的边集合。连接点边集合。连接点vi,vjV 的边记作的边记作vi,vj，或者或者vj,vi。如如果果一一个个图图是是由由点点和和弧弧所所构构成成的的，那那么么称称为为它它为为有有向向图图，记记作作D=(V,A)，其其中中V表表示示有有向向图图D的的点点集集合合，A表表示示有有向向图图D的的弧弧集集合合。一一条条方方向向从从vi 指指向向vj 的的弧弧，记记作作(vi,vj)。第13页，共146页，编辑于2022年，星期三例如例如.图图8.48.4是一个无向图是一个无向图G=（V，E），），其中其中V=v1,v2,v3,v4 E=v1,v2,v2,v1,v2,v3,v3,v4,v1,v4,v2,v4,v3,v3v3v2v1v4图图8.48.4第14页，共146页，编辑于2022年，星期三图图8.58.5 是一个有向图是一个有向图D=（V，A）其中其中V=v1,v2,v3,v4,v5,v6,v7 A=(v1,v2),(v1,v3),(v3,v2)(v3,v4),(v2,v4),(v4,v5),(v4,v6),(v5,v3),(v5,v4),(v5,v6),(v6,v7)图图8.5v7v5v3v4v2v6v1第15页，共146页，编辑于2022年，星期三下面介绍一些常用的名词：下面介绍一些常用的名词：一一个个图图G或或有有向向图图D中中的的点点数数,记记作作P(G)或或P(D),简简记记作作P,边数或者弧数边数或者弧数,记作记作q(G)或者或者q(D),简记作简记作q。如如果果边边 vi ,vj E,那那么么称称vi,vj 是是边边的的端端点点，或或者者vi,vj是是相相邻邻的的。如如果果一一个个图图G中中，一一条条边边的的两两个个端端点点是是相相同同的的,那那么么称称为为这这条条边边是是环环，如如图图8.48.4中中的的边边 v3,v3 是是环环。如如果果两两个个端端点点之之间间有有两两条条以以上上的的边边，那那么么称称为为它它们们为为多多重重边边，如如图图8.48.4中中的的边边v1,v2,v2,v1。一一个个无无环环，无无多多重重边边的的图图称称为为简简单单图图，一一个个无无环环，有有多多重重边的图称为多重图。边的图称为多重图。第16页，共146页，编辑于2022年，星期三 以以点点v为为端端点点的的边边的的个个数数称称为为点点v的的度度，记记作作d(v),如如图图8484中中d(v1)=3=3，d(v2)=4,=4,d(v3)=4,d(v4)=3。度度为为零零的的点点称称为为弧弧立立点点，度度为为1 1的的点点称称为为悬悬挂挂点点。悬悬挂挂点点的的边边称称为为悬悬挂挂边边。度度为为奇奇数数的的点称为奇点，度为偶数的点称为偶点。点称为奇点，度为偶数的点称为偶点。端点的度端点的度 d(v)：点：点 v 作为端点的边的个数作为端点的边的个数 奇点：奇点：d(v)=奇数；奇数；第17页，共146页，编辑于2022年，星期三偶点：偶点：d(v)=偶数；偶数；悬挂点：悬挂点：d(v)=1；悬挂边：悬挂边：与悬挂点连接的边；与悬挂点连接的边；孤立点：孤立点：d(v)=0；空图：空图：E=，无边图无边图v1v2v3v4v5v6第18页，共146页，编辑于2022年，星期三v1v7v6v5v4v3v2V=v1,v2,v3,v4,v5,v6 ,v7 d(v1)=3;d(v2)=5;d(v3)=4;d(v4)=4;d(v5)=1;d(v6)=3;d(v7)=0其中其中 v5 为悬挂点，为悬挂点，v7 为孤立点。为孤立点。第19页，共146页，编辑于2022年，星期三 定理定理8.18.1 所有顶点度数之和等于所有边数的所有顶点度数之和等于所有边数的2 2倍。倍。证明：证明：因为在计算各个点的度时，每条边被它因为在计算各个点的度时，每条边被它的两个端点个用了一次。的两个端点个用了一次。v1v5v4v3v2简单图简单图（2）（4）（3）（3）（2）v1v5v4v3v2多重图多重图（4）（6）（3）（3）（2）第20页，共146页，编辑于2022年，星期三定理定理8.28.2 在任一图中，奇点的个数必为偶数。在任一图中，奇点的个数必为偶数。证明：证明：设设 V1 1，V2 2 分别是图分别是图G中奇点和偶点的中奇点和偶点的 集合，由定理集合，由定理8.1 8.1，有，有因为因为 是偶数，是偶数，也是偶数，因此也是偶数，因此也必是偶数，从而也必是偶数，从而V1 中的点数是偶数。中的点数是偶数。第21页，共146页，编辑于2022年，星期三有向图中，以vi为始点的边数称为点vi的出次出次，用表示；以vi为终点的边数称为点vi的入次入次，用表示；vi点的出次和入次之和就是该点的次。结论：结论：所有顶点的入次之和等于所有顶点的出次之和。第22页，共146页，编辑于2022年，星期三图的连通性：图的连通性：链：链：由两两相邻的点及其相关联的边构成的点边由两两相邻的点及其相关联的边构成的点边序列。序列。如如:v0 ,e1 ,v1 ,e2 ,v2，e3 ,v3 ,vn-1,en，vn;v0，vn分别为链的起点和终点分别为链的起点和终点 。记作（。记作（v0 ,v1 ,v2，,v3 ,vn-1,vn）简单链：简单链：链中所含的边均不相同；链中所含的边均不相同；初等链：初等链：链中所含的点均不相同链中所含的点均不相同,也称通路；也称通路；圈：圈：若若 v0 vn 则称该链为开链，否则称则称该链为开链，否则称为为闭链或回路或圈闭链或回路或圈；第23页，共146页，编辑于2022年，星期三简单圈：简单圈：如果在一个圈中所含的边均不相同如果在一个圈中所含的边均不相同初等初等圈：圈：除起点和终点外链中所含的点均不除起点和终点外链中所含的点均不 相同的圈；相同的圈；连通图：连通图：图中任意两点之间均图中任意两点之间均 至少有一条通路，否则至少有一条通路，否则 称为不连通图。称为不连通图。v1v2v4v3v5v6v7v8v9初等链初等链:(v1,v2,v3,v6,v7,v5)初等圈：初等圈：(v1,v2,v3,v5,v4,v1)第24页，共146页，编辑于2022年，星期三简单圈：简单圈：(v4,v1,v2,v3,v5,v7,v6,v3,v4)简单链：简单链：(v1,v2,v3,v4 ,v5,v3)以后除特别声明，均指初等链和初等圈。以后除特别声明，均指初等链和初等圈。v1v2v3v4v5连通图连通图v1v5v4v3v2v6第25页，共146页，编辑于2022年，星期三子图定义：子图定义：如果如果 V2 V1,E2 E1 称称 G G2 2 是是 G G1 1 的子图；的子图；真子图：真子图：如果如果 V2 V1,E2 E1 称称 G2 是是 G1 的真子图；的真子图；部分图：部分图：如果如果 V2=V1,E2 E1 称称 G2 是是 G1 的部分图或支撑子图；的部分图或支撑子图；导出子图：导出子图：如果如果V V2 2 V V1 1,E2=vi,vj vi,vj V2,称称 G2 是是 G1 中由中由V2 导出导出的导出子图。的导出子图。设设 G G1 1=V=V1 1,E,E1 1,G,G2 2=V=V2 2,E,E2 2 第26页，共146页，编辑于2022年，星期三G G1 1第27页，共146页，编辑于2022年，星期三G G2 2真子图真子图第28页，共146页，编辑于2022年，星期三G G3 3子图子图部分图部分图第29页，共146页，编辑于2022年，星期三G G4 4导出子图导出子图第30页，共146页，编辑于2022年，星期三有向图：关联边有方向有向图：关联边有方向弧：弧：有向图的边有向图的边 a=(u,v),起点起点u,终点终点v；路：路：若有从若有从 u 到到 v 不考虑方向的链不考虑方向的链,且且 各方向一致各方向一致,则称之为从则称之为从u到到v 的路；的路；初等路初等路:各顶点都不相同的路；各顶点都不相同的路；初等回路初等回路:u=v 的初等路的初等路;连通图：连通图：若不考虑方向若不考虑方向 是无向连通图是无向连通图;强连通图：强连通图：任两点有路任两点有路;v1v2v3v4v5第31页，共146页，编辑于2022年，星期三8.2 树和最小支撑树树和最小支撑树一、树及其性质一、树及其性质 在在各各种种各各样样的的图图中中，有有一一类类图图是是十十分分简简单单又非常具有应用价值的图，这就是又非常具有应用价值的图，这就是树。树。例例8.38.3 已已知知有有六六个个城城市市，它它们们之之间间要要架架设设电电话话线线，要要求求任任意意两两个个城城市市均均可可以以互互相相通通话话，并并且电话线的总长度最短。且电话线的总长度最短。第32页，共146页，编辑于2022年，星期三如如果果用用六六个个点点v1 1v6 6代代表表这这六六个个城城市市，在在任任意意两两个个城城市市之之间间架架设设电电话话线线，即即在在相相应应的的两两个个点点之之间间连连一一条条边边。这这样样，六六个个城城市市的的一一个个电电话话网网就就作作成成一一个个图图。表表示示任任意意两两个个城城市市之之间间均均可可以以通通话话，这这个个图图必必须须是是连连通通图图。并并且且，这这个个图图必必须须是是无无圈圈的的。否否则则，从从圈圈上上任任意意去去掉掉一一条条边边，剩剩下下的的图图仍仍然然是是六六个个城城市市的的一一个个电电话话网网。图图8.88.8是一个不含圈的连通图，代表了一个电话线网。是一个不含圈的连通图，代表了一个电话线网。第33页，共146页，编辑于2022年，星期三图图8.8v6v3v4v2v5v1第34页，共146页，编辑于2022年，星期三 定义定义定义定义8.18.18.18.1 一个无圈的连通图叫做一个无圈的连通图叫做树树。下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质：下面介绍树的一些重要性质：定定定定理理理理8.38.38.38.3 设设图图G=（V，E）是是一一个个树树 P(G)2，那那么么图图G中至少有两个悬挂点。中至少有两个悬挂点。定定理理8.4 8.4 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G 不含圈，并且有且仅有不含圈，并且有且仅有P-1条边。条边。定定定定理理理理8.58.58.58.5 图图G=（V，E）是是一一个个树树的的充充要要条条件件是是G是是连通图，并且有且仅有连通图，并且有且仅有 p1 条边。条边。定定理理8.68.6 图图G是是一一个个树树的的充充分分必必要要条条件件是是任任意意两两个个顶顶点点之间有且仅有一条链。之间有且仅有一条链。第35页，共146页，编辑于2022年，星期三 从以上定理，不难得出以下从以上定理，不难得出以下结论结论：（1 1）从从一一个个树树中中任任意意去去掉掉一一条条边边，那那么么剩剩下下的的图图不不是是连连通通图图，亦亦即即，在在点点集集合合相相同同的的图图中，树是含边数最少的连通图。中，树是含边数最少的连通图。（2 2）在在树树中中不不相相邻邻的的两两个个点点之之间间加加上上一一条条边，那么恰好得到一个圈。边，那么恰好得到一个圈。二二.支撑树支撑树定义定义8.28.2 设图设图K=(V,EI)是图是图G=(V,E)的的第36页，共146页，编辑于2022年，星期三 一一支支撑撑子子图图，如如果果图图K=(V,EI)是是一一个个树树,那那么称么称K 是是G 的一个支撑树。的一个支撑树。例如例如,图图8.10b 8.10b 是图是图8.10a 8.10a 的一个支撑树的一个支撑树图图8.10v6v5v2v3v4v1av6v5v2v3v4v1b第37页，共146页，编辑于2022年，星期三 显然显然,如果图如果图K=(V,EI)是图是图G=(V,E)的一个支的一个支撑树撑树,那么那么K 的边数是的边数是p(G)-1，G中不属于支撑中不属于支撑树树K 的边数是的边数是q(G)-p(G)+1。定理定理8.78.7 一个图一个图G有支撑树的充要条件是有支撑树的充要条件是G 是是连通图连通图。证明：证明：充分性充分性:设图设图G是连通的，若是连通的，若G不含圈，不含圈，则按照定义，则按照定义，G是一个树，从而是一个树，从而G是自身的一个是自身的一个支撑树。若支撑树。若G含圈，则任取含圈，则任取G的的第38页，共146页，编辑于2022年，星期三一个圈，从该圈中任意去掉一条边，得到图一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图的一支撑子图G1。若若G1不含圈，则不含圈，则G1是是G的一个的一个支撑树。若支撑树。若G1仍然含圈，则任取仍然含圈，则任取G G1 1的一个圈，再的一个圈，再从圈中任意去掉一条边，得到图从圈中任意去掉一条边，得到图G的一支撑子的一支撑子图图G2。依此类推，可以得到图依此类推，可以得到图G的一个支撑子图的一个支撑子图GK，且不含圈，从而且不含圈，从而GK是一个支撑树。是一个支撑树。第39页，共146页，编辑于2022年，星期三 定理定理8.78.7充分性的证明，提供了一个寻找充分性的证明，提供了一个寻找连通图支撑树的方法叫做连通图支撑树的方法叫做“破圈法破圈法”。就是从。就是从图中任取一个圈，去掉一条边。再对剩下的图图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。到一个支撑树。例例8.48.4 用破圈法求出图用破圈法求出图8-118-11的一个支撑的一个支撑树。树。e e4 4e e6 6e e5 5e e3 3e e2 2e e1 1e e7 7e e8 8v3v2v1v4v5图图8-118-11第40页，共146页，编辑于2022年，星期三取一个圈取一个圈(v1,v2,v3,v1)，在一个圈中去掉边，在一个圈中去掉边e3 。在剩下的图中，再取一个圈（。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），），去掉边去掉边e4 。再从圈（。再从圈（v3,v4 v5,v3）中去掉边）中去掉边e6 。再从圈再从圈(v1,v2,v5,v4,v3,v1 ）中去掉边）中去掉边e7，这样，这样，剩下的图不含圈，于是得到一个剩下的图不含圈，于是得到一个 支撑树，如图支撑树，如图8.128.12所示。所示。v2e1e2e5e8v1v3v4v5图图8.128.12第41页，共146页，编辑于2022年，星期三三三.最小支撑树问题最小支撑树问题 定义定义8.38.3 如果图如果图G=（V，E），对于，对于G中的中的每一条边每一条边 vi,vj，相应地有一个数，相应地有一个数Wij，那么称，那么称这样的图这样的图G为赋权图，为赋权图，Wij称为边称为边 vi,vj 的权。这的权。这里所指的权，是具有广义的数量值。根据实际研究里所指的权，是具有广义的数量值。根据实际研究问题的不同，可以具有不同的含义。例如长度，费问题的不同，可以具有不同的含义。例如长度，费用、流量等等。用、流量等等。赋权图在图论及实际应用方面有着重要的赋权图在图论及实际应用方面有着重要的地位，被广泛应用于现代科学管理和工程技术地位，被广泛应用于现代科学管理和工程技术等领域，最小支撑树问题就是赋权图的最优化等领域，最小支撑树问题就是赋权图的最优化问题之一。问题之一。第42页，共146页，编辑于2022年，星期三 设设G=（V，E）是一个连通图，是一个连通图，G的每一条的每一条 vi,vj 对应一个非负的权对应一个非负的权Wij。定义定义8.48.4 如果图如果图T=（V，EI）是图是图G的一个的一个支撑树，那么称支撑树，那么称EI上所有边的权的和为支撑树上所有边的权的和为支撑树T的权，记作的权，记作S(T)。如果图如果图G的支撑树的支撑树T*的权的权S(T*)，在在G 的所的所有支撑树有支撑树T中的权最小，即中的权最小，即S(T*)=minTS(T)，那那么称么称T*是是G的最小支撑树。的最小支撑树。第43页，共146页，编辑于2022年，星期三如前所述，在已知的几个城市之间联结电话线网，如前所述，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，一个问题的要求总长度最短和总建设费用最少，一个问题的解决可以归结为最小支撑树问题。解决可以归结为最小支撑树问题。再如，城市间交通线的建造等，都可以归结为这再如，城市间交通线的建造等，都可以归结为这一类问题。一类问题。下面介绍寻求最小支撑树的方法下面介绍寻求最小支撑树的方法-破圈法破圈法。在给定的连通图中任取一个圈，去掉权最大的一条在给定的连通图中任取一个圈，去掉权最大的一条边，如果有两条以上权最大的边，则任意边，如果有两条以上权最大的边，则任意第44页，共146页，编辑于2022年，星期三去掉一条。在剩下的图中，重复以上步骤，直去掉一条。在剩下的图中，重复以上步骤，直到得到一个不含圈的连通图为止，这个图便是到得到一个不含圈的连通图为止，这个图便是最小支撑树。最小支撑树。例例8.58.5 某六个城市之间的道路网如图某六个城市之间的道路网如图8.138.13a 所示，要求沿着已知长度的道路联结六个城市所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。的电话线网，使得电话线的总长度最短。第45页，共146页，编辑于2022年，星期三图图8.13av3v2v1v4v6v553142图图8.13b3v6v5v2v3v46255441v17 73 3第46页，共146页，编辑于2022年，星期三 解：解：这个问题的解决就是要求所示赋权图这个问题的解决就是要求所示赋权图8.13a8.13a中的最小支撑树。用破圈法求解。任取一中的最小支撑树。用破圈法求解。任取一个圈，例如（个圈，例如（v1,v2,v3,v1 ），去掉这个圈中），去掉这个圈中权最大的边权最大的边 v1,v3。再取一个圈（。再取一个圈（v3,v5 ,v2 ,v3），去掉边），去掉边 v2,v5。再取一个圈（。再取一个圈（v3,v5,v4,v2 ,v3），去掉边），去掉边 v3,v5。再取一个圈（。再取一个圈（v5,v6,v4,v5），这个圈中，有两条权最大的边），这个圈中，有两条权最大的边 v5,v6 和和v4,v6。任意去掉其中的一条，例如。任意去掉其中的一条，例如 v5,v6。这时得到一个。这时得到一个第47页，共146页，编辑于2022年，星期三不含圈的图，如图不含圈的图，如图8.138.13b 所示，即是最小支撑所示，即是最小支撑树。树。关于破圈法正确性的证明略去。关于破圈法正确性的证明略去。例例 用破圈法求出下图中的最小支撑树用破圈法求出下图中的最小支撑树3122353223225422232222122第48页，共146页，编辑于2022年，星期三破圈法和生长法两个方法：破圈法和生长法两个方法：（1 1）在网络图中寻找一个圈。若不存在圈，则已）在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；经得到最短树或网络不存在最短树；（2 2）去掉该圈中权数最大的边；）去掉该圈中权数最大的边；反复重复反复重复 两步，直到最短树。两步，直到最短树。1.破圈法第49页，共146页，编辑于2022年，星期三从网络图中任意节点开始寻找与该节点关从网络图中任意节点开始寻找与该节点关联的权数最小的边，得到另一节点后，再联的权数最小的边，得到另一节点后，再从这个新节点开始寻找与该节点关联的权从这个新节点开始寻找与该节点关联的权数最小的另一边数最小的另一边。注意寻找过程中，。注意寻找过程中，节点不得重复，即在找最小权数边时不考节点不得重复，即在找最小权数边时不考虑已选过的边虑已选过的边,反复进行，直到得到最短反复进行，直到得到最短树或证明网络不存在最短树。树或证明网络不存在最短树。2.成长法第50页，共146页，编辑于2022年，星期三例例 用成长法求出下图中的最小支撑树（最短用成长法求出下图中的最小支撑树（最短 树）树）v1v2v3v4v5v6v7v1v2v3v4v5v6v731245223423122223第51页，共146页，编辑于2022年，星期三一一.引言引言 最最短短路路径径问问题题是是图图论论中中十十分分重重要要的的最最优优化化问问题题之之一一，它它作作为为一一个个经经常常被被用用到到的的基基本本工工具具，可可以以解解决决生生产产实实际际中中的的许许多多问问题题，比比如如城城市市中中的的管管道道铺铺设设，线线路路安安排排，工工厂厂布布局局，设设备备更更新新等等等等。也也可可以以用用于于解解决决其其它它的的最最优优化化问问题题。88.3 3最短路问题最短路问题第52页，共146页，编辑于2022年，星期三例例8 86 6 如图如图8.148.14所示的单行线交通网，每个所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有弧旁边的数字表示这条单行线的长度。现在有一个人要从一个人要从v v1 1出发，经过这个交通网到达出发，经过这个交通网到达v v8 8，要寻，要寻求是总路程最短的线路。求是总路程最短的线路。图图8.14v1v4v2v8v7v6v5v9636234102312624101第53页，共146页，编辑于2022年，星期三 从从v1到到v8 的路线是很多的。比如从的路线是很多的。比如从v1出发，出发，经过经过v2 ,v5到达到达v8 或者从或者从v1出发，经过出发，经过v4，v6，v7 到达到达v8 等等。但不同的路线，经过的总长等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是不同的。例如，按照第一个线路，总长度是度是6+1+6=136+1+6=13单位，按照第二个路线，总长单位，按照第二个路线，总长度是度是1+10+2+4=171+10+2+4=17单位。单位。从这个例子中，可以给出一般意义下的最短路从这个例子中，可以给出一般意义下的最短路问题。设一个赋权有向图问题。设一个赋权有向图D=（V，A），），第54页，共146页，编辑于2022年，星期三对于每一个弧对于每一个弧a=（vi,vj），相应地有一个权，相应地有一个权wij。Vs,vt是是D中的两个顶点，中的两个顶点，P 是是D中从中从vs到到vt 的任的任意一条路，定义路的权是意一条路，定义路的权是P P 中所有弧的权的中所有弧的权的和，记作和，记作S(p)。最短路问题就是要在所有从最短路问题就是要在所有从vs到到vt的路的路P0中，寻找一个权最小的路中，寻找一个权最小的路P0，亦即亦即S(P0)=minS(p)。P0 叫做从叫做从vs到到vs的最短路。的最短路。P0的权的权S S(P0)叫做从叫做从vs到到vt 的距离，记作的距离，记作d（vs，vt）。）。由于由于D是有向图，很明显是有向图，很明显d（vs，vt）与与d（vt，vs）一般不相等一般不相等。第55页，共146页，编辑于2022年，星期三 二二.Dijkstra算法算法 下下面面介介绍绍在在一一个个赋赋权权有有向向图图中中寻寻求求最最短短路路的的方方法法Dijkstra算算法法，它它是是在在19591959年年提提出出来来的的。目目前前公公认认，在在所所有有的的权权wij 00时时，这这个个算算法法是是寻寻求求最最短短路路问问题题最最好好的的算算法法。并并且且，这这个个算算法法实实际际上上也也给给出出了了寻寻求求从从一一个个始始定定点点vs到任意一个点到任意一个点vj的最短路。的最短路。第56页，共146页，编辑于2022年，星期三Dijkstra算法的基本思想是从算法的基本思想是从vs出发，逐步向外出发，逐步向外寻找最短路。在运算过程中，与每个点对应，寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表记录一个数，叫做一个点的标号。它或者表示从示从vs到该点的最短路权（叫做到该点的最短路权（叫做P P 标号），或者标号），或者表示从表示从v vs s 到该点最短路权的上界（叫做到该点最短路权的上界（叫做T 标号）标号）。算法的每一步是去修改。算法的每一步是去修改T标号，把某一个具标号，把某一个具有有T 标号的点改变为具有标号的点改变为具有P 标号的点，使图标号的点，使图D中中具有具有P 标号的顶点多一个。这样，至多经过标号的顶点多一个。这样，至多经过P-1 步，就可求出从步，就可求出从vs 到各点到各点vj 的最短路。的最短路。第57页，共146页，编辑于2022年，星期三 以以例例1 1为为例例说说明明这这个个基基本本思思想想。在在例例1 1中中，S=1。因因为为Wij 0，d（v1,v1）=0。这这时时，v1是是具具有有P标标号号的的点点。现现在在看看从从v1出出发发的的三三条条弧弧（v1,v2），（v1,v3）和和（v1,v4）。如如果果一一个个人人从从v1出出发发沿沿（v1,v2）到到达达v2，这这时时的的路路程程是是d（v1,v1）+w12=6单单位位。如如果果从从v1出出发发，沿沿（v1,v3）到到达达v3，则则是是d（v1,v1）+w13=3单单位位。同同理理，沿沿（v1,v4）到到达达v4，是是d（v1,v1）+w14=1单单位位。因因此此，他他从从v1出出发发到到达达v4的的最最短短路路必必是是（v1,v4），d（v1,v4）=1。第58页，共146页，编辑于2022年，星期三这是因为从这是因为从v v1 1到达到达v4的任一条路的任一条路P P，假如不是，假如不是（v1,v4），），则必先沿则必先沿（v1,v2）到达到达v2，或者沿，或者沿（v1,v3）到达到达v3，而这时的路程已是而这时的路程已是6 6或者或者3 3单单位。由于所有的权位。由于所有的权wij 0，因此，不论他如何再因此，不论他如何再从从v2 或者或者v3 到达到达v4，所经过的总路程都不会比所经过的总路程都不会比1 1少，于是就有少，于是就有d（v1,v4）=1。这样就使这样就使v4 变成具变成具有有P标号的点。现在看从标号的点。现在看从v1 和和v4指向其余点的弧。指向其余点的弧。如上所述，从如上所述，从v1出发，分别沿出发，分别沿（v1,v2），（），（v1,v3）到达到达v2，v3，经过经过第59页，共146页，编辑于2022年，星期三的路程是的路程是6 6或者或者3 3单位。从单位。从v4出发沿出发沿（v4 ,v6）到到达达v6，经过的路程是，经过的路程是d（v1,v4）+w46=1+10=11单位。而单位。而min d（v1,v1）+w12，d（v1,v1）+w13，d（v1,v4）+w46=d（v1,v1）+w13=3单位。单位。根据同样的理由，可以断定，从根据同样的理由，可以断定，从v1 1 到达到达v3 3的最的最短路是（短路是（v1,v3），），d（v1,v3）=3。这样，又使这样，又使点点v3 3变为具有变为具有P标号的点，不断重复以上过程，标号的点，不断重复以上过程，就可以求出从就可以求出从vs到达任一点到达任一点vj的最短路。的最短路。第60页，共146页，编辑于2022年，星期三(0,0)(6,1)(3,1)(1,1)(0,0)(3,1)(1,1)(6,1)(11,4)v1v4v2v8v7v6v5v9636234102312624101v3v1v4v2v8v7v6v5v9636234102312624101v3第61页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v2v6v5(6,1)(11,4)(0,0)(3,1)(1,1)(5,3)(11,4)v1v4v8v7v9636234102312624101v3v1v4v2v8v7v6v5v9636234102312624101v3第62页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v2(5,3)(11,4)(0,0)(3,1)(1,1)v4v2v610(5,3)(11,4)(6,2)v1v4v8v7v6v5v9636234102312624101v3v1v8v7v5v96362342312624101v3第63页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(11,4)(6,2)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第64页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第65页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)v3v3第66页，共146页，编辑于2022年，星期三(0,0)(3,1)(1,1)v1v4v2v8v7v6v5v9636234102312624101(5,3)(10,5)(6,2)(9,5)(12,5)从从v1 到到 v8 的最短路的长度为：的最短路的长度为：12从从v1 到到 v8 的最短路线为