《运筹学》课程授课教案（讲稿）第16讲 树与最短路

课程名称：《运筹学》第_16_讲次1、图与网络的基本知识2、树授课题目3、最短路问题本讲目的要求及重点难点：【目的要求】1、正确理解图的基本概念与基本定理；2、理解树与最小支撑数的概念及求最小树的算法，理解欧拉图与最优投递路线问题的解法；3、熟练掌握赋权的最短通路问题及其Dijkstra算法，[重点及难点】求最短路问题。内容[本讲课程的引入]图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来越受到工程技术人员和经营管理人员的重视。[本讲课程的内容]一、图与网络的基本知识1、图与网络的基本概念在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样的示意图。我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并不重要，因此，图论中的图与几何图形或工程制图等本质上是不同的

课程名称：《运筹学》 第 16 讲次 授课题目 1、图与网络的基本知识 2、树 3、最短路问题 本讲目的要求及重点难点： 目的要求] 1、正确理解图的基本概念与基本定理；2、理解树与最小支撑数的概念及求 最小树的算法，理解欧拉图与最优投递路线问题的解法；3、熟练掌握赋权的最短通路问 题及其 Dijkstra 算法， [重点及难点] 求最短路问题。 内 容 [本讲课程的引入] 图论是应用非常广泛的运筹学分支，它已经广泛地应用于物理学控制论，信息论，工程技术，交 通运输，经济管理，电子计算机等各项领域。对于科学研究，市场和社会生活中的许多问题，可以同 图论的理论和方法来加以解决。例如，各种通信线路的架设，输油管道的铺设，铁路或者公路交通网 络的合理布局等问题，都可以应用图论的方法，简便、快捷地加以解决。随着科学技术的进步，特别 是电子计算机技术的发展，图论的理论获得了更进一步的发展，应用更加广泛。如果将复杂的工程系 统和管理问题用图的理论加以描述，可以解决许多工程项目和管理决策的最优问题。因此，图论越来 越受到工程技术人员和经营管理人员的重视。 [本讲课程的内容] 一、 图与网络的基本知识 1、 图与网络的基本概念 在实际的生产和生活中，人们为了反映事物之间的关系，常常在纸上用点和线来画出各式各样 的示意图。我们用点和点之间的线所构成的图，反映实际生产和生活中的某些特定对象之间的特定关 系。一般来说，通常用点表示研究对象，用点与点之间的线表示研究对象之间的特定关系。由于在一 般情况下，图中的相对位置如何，点与点之间线的长短曲直，对于反映研究对象之间的关系，显得并 不重要，因此，图论中的图与几何图形或工程制图等本质上是不同的

内容定义1一个图是由点集V=和V中元素的无序对的一个集合E=(e所构成的二元组，记为G-(V，E)，其中V中的元素v,叫做顶点，V表示图G的点集合：E中的元素e,叫做边，E表示图G的边集合。例8.1在图8—2中：V=(11,'2,1'3,V4,'s,Ve)E=(e,e,es,ey,es,es,er,eg,eg,eo)eio其中ei=(vi,V2)，e2=(i,V2)e, =(v2,V3], ex =(V3,V4,图8—2e,=(11,V3),eg=(V3,Vs),en=(V3,Vs),eg=(vs,V6),eg=(V6,Ve],e1o=(v1,V6)如果两个点u,veV，且边(u,")eE，则称u,v两点相邻。u,v称为边(u,v)的端点。如果两条边er,e,eE，且它们有一个公共端点u，则称e,e,相邻，边ei,e,称为点u的关联边。通常，我们把点与点之间不带箭头的线叫做边，带箭头的线（V中元素的有序对）叫做弧。如果一个图是由点和边所构成的，则称其为无向图，记作G=(V，E)，连接点的y，eV边记作[vi,，或者[yj.。图8—2是无向图。如果一个图是由点和弧所构成的，那么称为它为有向图，记作D=(V,A)，其中V表示有向图D的点集合，A表示有向图D的弧集合。一条方向从vi指向y的弧，记作(vi.y)。图8—3为有向图。其中=(,24V%)A= ((11, 1), (12, V), (/2, 15),(12, V5), (13, V5s), (v4, Vs ),图8—3(vs, V4), (vs, V6) )一条边的两个端点是相同的，那么称为这条

内 容 定义 1 一个图是由点集 V  v j 和 V 中元素的无序对的一个集合 { }k E  e 所构成的 二元组，记为 G=(V，E)，其中 V 中的元素 j v 叫做顶点，V 表示图 G 的点集合；E 中的元 素 k e 叫做边，E 表示图 G 的边集合。 例 8.1 在图 8—2 中： V  v1 ,v2 ,v3 ,v4 ,v5 , v6  { , , , , , , , , } 1 2 3 4 5 6 7 8 9 10 E  e ，e e e e e e e e e 其中 { , } 1 1 2 e  v v ， { , } 2 1 2 e  v v ， { , } 3 2 3 e  v v ， { , } 4 3 4 e  v v ， { , } 5 1 3 e  v v ， { , } 6 3 5 e  v v ， { , } 7 3 5 e  v v ， { , } 8 5 6 e  v v ， { , } 9 6 6 e  v v ， { , } 10 1 6 e  v v 。 如果两个点 u,v V ，且边 (u,v) E ，则称 u,v 两点相邻。u,v 称为边 (u,v) 的端 点。 如果两条边 ei , ej  E ，且它们有一个公共端点 u ，则称 i j e , e 相邻，边 i j e , e 称为点 u 的关联边。 通常，我们把点与点之间不带箭头的线叫做边，带箭头的线（V 中元素的有序对）叫 做弧。如果一个图是由点和边所构成的，则称其为无向图，记作 G=(V，E)，连接点的 vi , v j V 边记作[vi , vj ]，或者[vj , vi ]。 图 8—2 是无向图。 如果一个图是由点和弧所构成的，那么称为它为有向图，记作 D=(V, A)，其中 V 表示 有向图 D 的点集合，A 表示有向图 D 的弧集合。一条方向从 vi 指向 vj 的弧，记作(vi , vj )。 图 8—3 为有向图。 其中 V = {v1 , v2 , v3 , v4 , v5 , v6 }， A = {(v1 , v3 ) , (v2 , v1) , (v2 , v3 ) , (v2 , v5 ) , (v3 , v5 ) , (v4 , v5 ) , (v5 , v4 ) , (v5 , v6 ) } 一条边的两个端点是相同的,那么称为这条 v1 v2 v3 v4 v5 v6 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 图 8—2 v4 v6 v1 v2 v3 v5 图 8—3

内容边是环。如图8—2中的边（%%）是环。如果两个端点之间有两条以上的边，那么称为它们为多重边。如图8—2中的边（"），（2"）。定义2一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。定义3每一对顶点间都有边相连的无向简单图称为完全图。有n个顶点的无向完全图记作K，。有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。定义4以点为端点的边的个数称为点v的度，记作d(v)。例如在图8—2中，d(v)=4，d(%)=4。度为零的点称为弧立点，度为1的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数的点称为奇点，度为偶数的点称为偶点。定理1所有顶点度数之和等于所有边数的2倍。证明因为在计算各个点的度时，每条边被它的两个端点各用了一次。定理2在任一图中，奇点的个数必为偶数。证明设V1，V2分别是图G中奇点和偶点的集合，由定理1，有d(v)+d(v)=d(v)=2q因为d(v)是偶数，d()vEVveNveN也是偶数，因此d(v)也必是偶数，从而V1中的点数是偶数。veN定义5有向图中，以v,为始点的边数称为点v的出次，用d+（y）表示；以v为终点的边数称为点v,的入次，用d-(v）表示：V,点的出次和入次之和就是该点的次。结论：所有顶点的入次之和等于所有顶点的出次之和。定义6设Gj=（V1,E1），G2=（V2,E2）如果V2V1,E2CE1称G2是GI的子图：如果V2=V1,E2CE1称G2是G1的部分图或支撑子图。2enSVe6Pei56es2O(c)(a)(bh)图8—4

内 容 边是环。如图 8—2 中的边（v 6 ,v6）是环。如果两个端点之间有两条以上的边，那么 称为它们为多重边。如图 8—2 中的边（v 1 ,v2） ，（v 2 ,v1）。 定义 2 一个无环，无多重边的图称为简单图，一个无环，有多重边的图称为多重图。 定义 3 每一对顶点间都有边相连的无向简单图称为完全图。有 n 个顶点的无向完全 图记作 Kn 。 有向完全图则是指任意两个顶点之间有且仅有一条有向边的简单图。 定义 4 以点 v 为端点的边的个数称为点 v 的度，记作 d(v) 。 例如在图 8—2 中，d(v1)= 4，d(v6)= 4。 度为零的点称为弧立点，度为 1 的点称为悬挂点。悬挂点的边称为悬挂边。度为奇数 的点称为奇点，度为偶数的点称为偶点。 定理 1 所有顶点度数之和等于所有边数的 2 倍。 证明 因为在计算各个点的度时，每条边被它的两个端点各用了一次。 定理 2 在任一图中，奇点的个数必为偶数。 证明 设 V1，V2 分别是图 G 中奇点和偶点的集合，由定理 1 ，有          1 2 ( ) ( ) ( ) 2 v V v V v V d v d v d v q 因为  vV d(v) 是偶数，   2 ( ) v V d v 也是偶数，因此   1 ( ) v V d v 也必是偶数，从而 V1 中的点数是偶数。 定义 5 有向图中，以 i v 为始点的边数称为点 i v 的出次，用 ( ) i d v  表示；以 i v 为终 点的边数称为点 i v 的入次，用 ( ) i d v  表示； i v 点的出次和入次之和就是该点的次。 结论：所有顶点的入次之和等于所有顶点的出次之和。 定义 6 设 G1 =（ V1 , E1 ），G2 =（ V2 ,E2 ）如果 V2 V1 , E2 E1 称 G2 是 G1 的子图；如果 V2 = V1 , E2 E1 称 G2 是 G1 的部分图或支撑子图。 e5 e7 v1 v2 v6 v5 v7 e1 e6 e8 (b) v1 v2 v3 v4 v5 v6 v7 e1 e6 e7 e9 e10 e11 (c) v1 v2 v3 v4 v6 v5 v7 e1 e2 e3 e4 e5 e6 e7 e8 e9 e10 e11 (a) 图 8—4

内容在图8一4中（b）为（a）的子图，（c）为（a）的子图在实际应用中，给定一个图G=（V，E）或有向图D=（V，A），在V中指定两个点，一个称为始点（或发点），记作，一个称为终点（或收点），记作，其余的点称为中间点。对每一条弧（"，)EA，对应一个数Wij，称为弧上的“权”。通常把这种赋权的图称为网络。2、连通图定义7由两两相邻的点及其相关联的边构成的点边序列称为链。如:。，eV,e22e，a，m,记作（o，，P2,)其链长为n，其中v。，v分别称为链的起点和终点。若链中所含的边均不相同，则称此链为简单链；所含的点均不相同的链称为初等链，也称通路。e3e1V3e6VsV5图8—6在图8—5图8s5(，e4，4，e7，v，e7，图，，%1为一条链，起点为2，终点为%，链长为4S=(，e4，V4，e7，'s，es，4，eg，%1为一条连接2和%简单链。S,=z，e4，4，eg，%为一条连接和%初等链。。与"，的一条链，若"。≠，则称该链为开链，否则称为闭链或回路或圈；如果在一个圈中所含的边均不相同，称此圈为简单圈；除起点和终点外链中所含的点均不相同的圈，叫做初等圈。在图8—5中，S={，，，e4，4，es，，2，]为一个圈。在图8—6中，S={y，es，es，4，es，）为一个圈，且为初等圈。定义9图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的分图

内 容 在图 8—4 中（b）为（a）的子图，（c）为（a）的子图 在实际应用中，给定一个图 G=（V，E）或有向图 D=（V，A），在 V 中指定两个点， 一个称为始点（或发点），记作 v1 ，一个称为终点（或收点），记作 v n ，其余的点称为 中间点。对每一条弧 (vi ,v j ) A ，对应一个数 wi j ，称为弧上的“权”。通常把这种赋权 的图称为网络。 2、 连通图 定义 7 由两两相邻的点及其相关联的边构成的点边序列称为链。 如:v 0 ，,e1， v 1，,e2，v 2，e 3 ， v 3 ,.,v n-1 , e n ， v n，记作（ v 0 ， v 1 ， v 2， v 3 , ., v n-1 ， v n ）， 其链长为 n ，其中 v 0 ，v n分别称为链的起点和终点 。若链中所含的边均不相同，则称此 链为简单链；所含的点均不相同的链称为初等链 , 也称通路。 在图 8—5 中，S1 ={v 2 ，e4 ，v4 ，e 7 ，v5 ，e 7 ，v4 ，e 9 ，v6 }为一条链，起点 为 v 2 ，终点为 v6 ，链长为 4。 S2 ={v 2 ，e4 ，v4 ，e 7 ，v5 ，e 8 ，v4 ，e 9 ，v6 }为一条连接 v 2 和 v6 简单链。 S3 ={v 2 ，e4 ，v4 ， e 9 ，v6 }为一条连接 v 2 和 v6 初等链。 v 0 与 v n 的一条链，若 v 0 ≠ v n 则称该链为开链，否则称为闭链或回路或圈；如果 在一个圈中所含的边均不相同，称此圈为简单圈；除起点和终点外链中所含的点均不相同 的圈，叫做初等圈。 在图 8—5 中，S3 ={ v 1，,e 1 ，v 2 ，e4 ，v4 ， e5 ，v 3 ，e 2 ，v 1 }为一个圈。 在图 8—6 中，S ={ v 3，,e 6，v 5 ，e8 ，v4 ，e 5 ，v3 }为一个圈，且为初等圈。 定义 9 图中任意两点之间均至少有一条通路，则称此图为连通图，否则称为不连通 图。任何一个不连通图都可以分为若干个连通子图，每一个称为原图的分图。 e 3 v 1 v 2 v 3 v4 v5 e7 e8 v6 ,e 1 e 2 e4 e5 e6 e9 e10 图 8—5 e 3 e7 v e8 1 v 2 v 3 v4 v5 v6 ,e 1 e 2 e4 e5 e6 e9 e10 图 8—6

内容二、树1、树的概念和性质在各种各样的图中，有一类图是十分简单又非常具有应用价值，这就是树。例8.3已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点，…，代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就做成一个图。表示任意两个城市之间均可以V通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图8一8是一个不含圈的连通图，代表了一个电话线网。图8—8定义13一个连通的无圈的无向图叫做树。树中次为1的点称为树叶，次大于1的点称为分支点。作为树T的定义，下列定义是等价的：（1）T是一个树。（设其顶点数为n，边数为m）(2）T无圈，且m=n-1。（3）T连通，且m=n-1。（4）T无圈，但在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。（5）T中任意两个顶点之间有且仅有一条链。（6）T连通，但去掉T的任一条边，T就不连通。由定理3很容易得出以下结论：从一个树中任意去掉一条边，那么剩下的图不是连通图，亦即，在点集合相同的图中，树是含边数最少的连通图。2、图的生成树定义14设图K=(V,E)是图G=(V,E)的一支撑子图，如果图K=(V,E)是一个V4(b)(a)图8—9

内 容 二、树 1、 树的概念和性质 在各种各样的图中，有一类图是十分简单又非常具有应用价值，这就是树。 例 8.3 已知有六个城市，它们之间 要架设电话线，要求任意两个城市均可以互相 通话，并且电话线的总长度最短。如果用六个点 v 1 ，.，v 6代表这六个城市，在任意两个 城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话 网就做成一个图。表示任意两个城市之间均可以 通话，这个图必须是连通图。并且，这个图必须 是无圈的。否则，从圈上任意去掉一条边，剩下 的图仍然是六个城市的一个电话网。图 8—8 是 一个不含圈的连通图，代表了一个电话线网。 定义 13 一个连通的无圈的无向图叫 做树。树中次为 1 的点称为树叶，次大于 1 的点称为分支点。 作为树 T 的定义，下列定义是等价的： （1）T 是一个树。（设其顶点数为 n ，边数为 m ） （2）T 无圈，且 m  n 1。 （3）T 连通，且 m  n 1。 （4）T 无圈，但在树中不相邻的两个点之间加上一条边，那么恰好得到一个圈。 （5）T 中任意两个顶点之间有且仅有一条链。 （6）T 连通，但去掉 T 的任一条边，T 就不连通。 由定理 3 很容易得出以下结论：从一个树中任意去掉一条边，那么剩下的图不是连通图， 亦即，在点集合相同的图中，树是含边数最少的连通图。 2、 图的生成树 定义 14 设图 ( , ) K  V E1 是图 G=(V , E )的一支撑子图， 如果图 ( , ) K  V E1 是一个 v 1 v 2 v 3 v 4 v 5 v 6 图 8—8 v 1 v 2 v 3 v 4 v 5 （a） v 1 v 2 v 3 v 4 v 5 （b） 图 8—9

内容树,那么称K是G的一个生成树（支撑树），或简称为图G的树。图G中属于生成树的边称为树枝，不在生成树中的边称为弦。在图8—9中，图（b）是图（a）的生成树。定理4一个图G有生成树的充要条件是G是连通图。证明必要性显然。充分性：设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个生成树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G不含圈，则G1是G的一个生成树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个生成树。定理4充分性的证明，提供了一个寻找连通图生成树的方法叫做“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个生成树。例8.4用破圈法求出图8一10的一个生成树。取一个圈(v1，2，V3，)，在一个圈中去掉边e。在剩下的图中，再取一个圈（y，"2，V4，V3，)，图8——10去掉边e。再从圈（v2，4，Vs，vz）中去掉边e。再从圈（V2V4"，13)中去掉边e，这样，剩下的图不含圈，于是得到一个生成树，如图8一11所示。显然，图的生成树不是.1唯一的。相对于破圈法，还有一种求生成树的方法叫做避圈V3法。此种方法为，在已给出的图G中，每步选一条边图8—11使它与已选出的边不构成圈，直

内 容 树,那么称 K 是 G 的一个生 成树（支撑树），或简称为图 G 的树。 图 G 中属于生成树的边称为树枝，不在 生成树中的边称为弦。 在图 8—9 中，图（b）是图（a）的生成树。 定理 4 一个图 G 有生成树的充要条件是 G 是连通图。 证明 必要性显然。 充分性: 设图 G 是连通的，若 G 不含圈，则按照定义，G 是一个树，从而 G 是自身 的一个生成树。若 G 含圈，则任取 G 的一个圈，从该圈中任意去掉一条边，得到图 G 的 一支撑子图 G1。若 G1 不含圈，则 G1 是 G 的一个生成树。若 G1 仍然含圈，则任取 G1 的一个圈，再从圈中任意去掉一条边，得到图 G 的一支撑子图 G2。依此类推，可以得到 图 G 的一个支撑子图 GK，且不含圈，从而 GK 是一个生成树。 定理 4 充分性的证明，提供了一个寻找连通图生成树的方法叫做“破圈法”。就 是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止， 这样就得到一个生成树。 例 8.4 用破圈法求出图 8—10 的一个生成树。 取一个圈 (v1， v 2，v 3， v 1 )， 在一个圈中去掉边 e 3 。在剩下的图中， 再取一个圈（v 1， v 2， v 4，v 3，v 1）， 去掉边 e 5 。再从圈（v 2，v 4，v 5， v 2） 中去掉边 e 7 。再从圈 (v 1，v 2，v 4，v 5， v 3，v 1 ) 中去掉边 e 1，这样，剩下的图不含圈，于是得到 一个生成树，如图 8—11 所示。显然，图的生成树不是 唯一的。 相对于破圈法，还有一种求生成树的方法叫做避圈 法。此种方法为，在已给出的图 G 中， 每步选一条边， 使它与已选出的边不构成圈，直 v 1 v 2 v 3 v 4 v 5 图 8——10 e1 e2 e3 e4 e5 e6 e7 e8 v 1 v 2 v 3 v 4 v 5 图 8—11 e2 e4 e6 e8

内容到选够n-1条边为止。此种方法也叫做加边法。3、最小生成树问题赋权图在图论及实际应用方面有着重要的地位被广泛应用于现代科学管理和工程技术等领域最小生成树问题就是赋权图的最优化问题之一。定义15如果图K=(V,E）是图G的一个生成树，那么称E,上所有边的权的和为生成树T的权，记作S(T)。如果图G的生成树T*的权S(T*)在G的所有生成树T中的权最小，即S(T")=minS(T)，那么称T*是G的最小生成树。下面介绍寻求最小生成树的两种方法。算法1（Kruskal算法）此法类似于求生成树的“避圈法”，基本步骤如下：先选出一条权最小的边，从这条边出发，继续从余下的边中选取权小且与已选出的边所构成的图不构成圈的边添加进去，直到选出n一1条边为止。例8.5某六个城市之间的道路网如图8一12（a）所示，要求沿着已知长度的道路联结六个城市的电话线网，使得电话线的总长度最短。SR图8—12(a)图8—12 (b)图812得图8一12(b)，就是所给图的一棵最小树，即六个城市之间最短的电话线网。它的权为15。定理5用Kruskal算法得到的子图T=(er，e2，…,en-）是一棵最小树。算法2（破圈法）

内 容 到选够 n 1 条边为止。此种方法也叫做加边法。 3、最小生成树问题 赋权图在图论及实际应用方面有着重要的地位， 被广泛应用于现代科学管理和工程技术等领域， 最小生成树问题就是赋权图的最优化问题之一。 定义 15 如果图 ( , ) K  V E1 是图 G 的一个生成树， 那么称 E1 上所有边的权的和为生成树 T 的权，记作 S(T)。如果图 G 的生成树 T *的权 S(T*)， 在 G 的所有生成树 T 中的权最小，即 ( ) min ( ) * S T S T T  ，那么称 T*是 G 的最小生成树。 下面介绍寻求最小生成树的两种方法。 算法 1 （Kruskal 算法） 此法类似于求生成树的“避圈法”，基本步骤如下： 先选出一条权最小的边，从这条边出发，继续从余下的边中选取权小且与已选出的边 所构成的图不构成圈的边添加进去，直到选出 n 1 条边为止。 例 8.5 某六个城市之间的道路网如图 8—12 (a) 所示，要求沿着已知长度的道路联结 六个城市的电话线网，使得电话线的总长度最短。 得图 8—12 (b)，就是所给图的一棵最小树，即六个城市之间最短的电话线网。它的权 为 15。 定理 5 用 Kruskal 算法得到的子图 ( , , , ) 1 2 1 *  n T e e  e 是一棵最小树。 算法 2 （破圈法） v 1 v 2 v 3 v 4 v 5 v 6 6 5 1 5 7 2 3 4 4 图 8—12 (a) v 1 v 2 v 3 v 4 v 5 v 6 5 1 2 3 4 图 8—12 (b) 图 8——12

内容此方法类似于求生成树的“破圈法”，基本步骤为先从图G中任取一个圈，去掉这个圈中权最大的边。再取一个圈，再去掉这个圈中权最大的边，重复此做法，检查剩余的圈，直到图中再没有圈为止。例8.6用破圈法计算例8.5中的六个城市之间最短的电话线网。任取一个圈，例如（，"2，"，），去掉这个圈中权最大的边(y)再取一个圈（，"52，），去掉边（2，5)。再取一个圈图（"，"42，），去掉边（，v)。再取一个圈（vs，，V4，v)，这个圈中，有两条权最大的边（vs，v）和（y4，"）。任意去掉其中的一条，例如（v，%)。这时得到一个不含圈的图，如图8一12（b）所示，即是最小生成树。三、最短路问题最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。最短路的一般提法为：设G=(V,E)为连通图，图中各边(v，V,)有权l，（l,=+o0表示，"之间没有边），，为图中任意两点，求一条路μ，使它为从到的所有路中总权最短。即：L(μ)= l(M.M)ED最小。求解最短路的方法很多，该问题完全可以看成一个网络问题，可以利用后面的最小费用流算法可以求解，也可以用前面介绍的动态规划方法求解。但计算效率最高的还是图论的方法。下面介绍几种算法。88.3.1狄克斯屈拉(Dijkstra)算法Dijkstra算法的基本思想是：从vs出发，逐步向外寻找最短路。在运算过程中，与每个点对应，记录一个数，叫做一个点的标号。它或者表示从"s到该点的最短路权叫做P标号，为永久性标号（permanetlabel)。或者表示从vs到该点最短路权的上界，叫做T标号，为试探性标号（tentativelabel)。算法的每一步是去修改T标号，把某一个具有T

内 容 此方法类似于求生成树的“破圈法”，基本步骤为： 先从图 G 中任取一个圈，去掉这个圈中权最大的边。再取一个圈，再去掉这个圈中权 最大的边，重复此做法，检查剩余的圈，直到图中再没有圈为止。 例 8.6 用破圈法计算例 8.5 中的六个城市之间最短的电话线网。 任取一个圈，例如（ v 1 ，v 2 ，v 3 ，v 1 ），去掉这个圈中权最大的边(v 1 ,v 3 )再取一个 圈（ v 3， v 5， v 2，v 3），去掉边（v2 ， v5）。再取一个圈（ v 3， v 5，v 4 , v 2，v 3），去掉 边（v 3 ，v 5）。再取一个圈（v 5，v 6 ，v 4 ， v 5），这个圈中，有两条权最大的边（v 5 ，v 6） 和（v 4 ，v 6）。任意去掉其中的一条，例如（v 5 ，v 6）。这时得到一个不含圈的图，如图 8 —12（b） 所示，即是最小生成树。 三、 最短路问题 最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工 具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设 备更新等等。也可以用于解决其它的最优化问题。 最短路的一般提法为：设 G  (V , E) 为连通图，图中各边 ( , ) i j v v 有权 i j l （ l i j   表示 i j v , v 之间没有边）， s t v , v 为图中任意两点，求一条路  ，使它为从 s v 到 t v 的所有 路中总权最短。即：      ( , ) ( ) i j v v i j L l 最小。 求解最短路的方法很多，该问题完全可以看成一个网络问题，可以利用后面的最小费 用流算法可以求解，也可以用前面介绍的动态规划方法求解。但计算效率最高的还是图论 的方法。下面介绍几种算法。 §8.3.1 狄克斯屈拉(Dijkstra)算法 Dijkstra 算法的基本思想是：从 vs 出发，逐步向外寻找最短路。在运算过程中，与 每个点对应，记录一个数，叫做一个点的标号。它或者表示从 vs 到该点的最短路权叫做 P 标号，为永久性标号（permanet label）。或者表示从 vs 到该点最短路权的上界，叫做 T 标号，为试探性标号（tentative label）。算法的每一步是去修改 T 标号，把某一个具有 T

内容标号的点改变为具有P标号的点，使图D中具有P标号的顶点多一个。这样，对于有n个顶点的图，至多经过n-1步，就可求出从始点vs到各点y及终点v,的最短路。算法步骤：1.给始点vs以P标号P(v)=0，这表示从vs到vs的最短距离为0，其余节点均给T标号，P(v)=+oo (i=2,3,,n)。（2）设节点v,为刚得到P标号的点，考虑点Vj，其中(V，,）eE，且v,为T标号。对,的T标号进行如下修改：T(v,)=min[T(v,), P(v,)+1,]（3）比较所有具有T标号的节点，把最小者改为P标号，即：P(v) = min[T(v,)]当存在两个以上最小者时，可同时改为P标号。若全部节点均为P标号，则停止，否则用V代替V,，返回步骤（2)。例 8.7 用Dijkstra算法求图8—13中从y到v.的最短路，解（1）首先给以P标号，P(v)=0，给其余所有点T标号，T(v)=+oo (i=2,3,.,6)3(2) 由于(vi,V2),(vi,V3)E,且图8—13"2、"为T标号，所以修改这两个标号：T(v2)= min[T(v2), P(v))+ /2]=min[+0, 0 +3] = 3T(v3)= min[T(v,), P(v)+l13] =min[+00, 0 + 5] = 5（3）比较所有T标号，T(vz)最小，所以令P(vz)=3（4)为刚得到P标号的点，考察边(121),(2,V),(2,V5）的端点，"，"。T(vs)= min[T(v3), P(v2)+/23] = min[5, 3+1] = 4T(v4) =min[T(v4), P(v2)+ 124] = min[+o0, 3+2] = 5

内 容 标号的点改变为具有 P 标号的点，使图 D 中具有 P 标号的顶点多一个。这样，对于有 n 个 顶点的图，至多经过 n 1 步，就可求出从始点 vs 到各点 vj 及终点 t v 的最短路。 算法步骤： 1.给始点 vs 以 P 标号 P(vs )  0 ，这表示从 vs 到 vs 的最短距离为 0，其余节点均给 T 标号， P(v ) (i 2,3, ,n) i     。 （2）设节点 i v 为刚得到 P 标号的点，考虑点 j v ，其中 (vi , v j ) E ，且 j v 为 T 标号。 对 j v 的 T 标号进行如下修改： ( ) min[ ( ), ( ) ] j j i i j T v  T v P v  l 。 （3）比较所有具有 T 标号的节点，把最小者改为 P 标号，即： ( ) min[ ( )] k i P v  T v 当存在两个以上最小者时，可同时改为 P 标号。若全部节点均为 P 标号，则停止，否则用 k v 代替 i v ，返回步骤（2）。 例 8.7 用 Dijkstra 算法求图 8—13 中从 1 v 到 6 v 的最短路。 解 （1）首先给 v 1以 P 标号， P(v1 )  0 ，给其余所有点 T 标号， T(v )   (i  2,3,  ,6) i （2）由于 (v1 ,v2 ),(v1 ,v3 ) E ，且 v 2、v 3为 T 标号，所以修改这两个标号： T(v2 )  min[T(v2 ), P(v1 )  l 1 2 ]  min[, 0  3]  3 T(v3 )  min[T(v3 ), P(v1 )  l 1 3]  min[, 0  5]  5 （3）比较所有 T 标号， ( ) 2 T v 最小，所以令 P(v2 )  3 （4）v 2 为刚得到 P 标号的点，考察边 ( , ),( , ),( , ) 2 3 2 4 2 5 v v v v v v 的端点 v 3，v 4 ，v 5 。 T(v3 )  min[T(v3 ), P(v2 )  l 2 3]  min[5, 31]  4 T(v4 )  min[T(v4 ), P(v2 )  l 2 4 ]  min[, 3 2]  5 v 1 v 2 v 3 v 4 v 6 v 5 3 5 2 2 4 2 4 2 图 8—13 1

内容T(vs) =min[T(vs), P(v2)+/2s]= min[+o0, 3+2] = 5（5）比较所有T标号，（4）中的T(v3）最小，所以令P(vs）=4（6）为刚得到P标号的点，检查边(v3Vs）的端点ys。T(vs)= min[T(vs), P(v3)+ 135]= min[6, 4 +4] = 8(7）全部T标号中，T(v4)与（4）中的T(vs)最小，所以令P(v4)=5，P(vs)=5（8）考察点4。T(v.) = min[T(v.), P(v4) + 146]= min[+00, 5 + 4] = 9（9）考察点"T(v6) =min[T(v), P(vs)+l56]= min[+00, 5+2] = 7（10）只有一个T标号中，T(%），令P(%)=7，计算结束。V2(3)全部计算结果见图8—14，V4 (5)V到v的最短路为1(0) VV→V2→1s →V64(4)13's (5)路长P(v)=7。图8-14事实上，在得到v到v的最短路的同时，还得到了到其它各点的最短路。应该注意的是，本算法只适用全部权为非负的情况，如果某边上权为负的，此算法不能使用。[本讲小结】今天我们学习了图的基本概念与基本定理、树与最小支撑数的概念及求最小树的算法、最短通路问题及其Dijkstra算法，希望大家课下要很好的复习

内 容 T(v5 )  min[T(v5 ), P(v2 )  l 2 5 ]  min[, 3 2]  5 （5）比较所有 T 标号，（4）中的 ( ) 3 T v 最小，所以令 P(v3 )  4 （6）v 3 为刚得到 P 标号的点，检查边 ( , ) 3 5 v v 的端点 v 5 。 T(v5 )  min[T(v5 ), P(v3 )  l 3 5 ]  min[6, 4  4]  8 （7）全部 T 标号中， ( ) 4 T v 与（4）中的 ( ) 5 T v 最小，所以令 P(v4 )  5， P(v5 )  5 （8）考察点 v 4 。 T(v6 )  min[T(v6 ), P(v4 )  l 4 6 ]  min[, 5  4]  9 （9）考察点 v 5 T(v6 )  min[T(v6 ), P(v5 )  l 5 6 ]  min[, 5  2]  7 （10）只有一个 T 标号中， ( ) 6 T v ，令 P(v6 )  7 ，计算结束。 全部计算结果见图 8—14， 1 v 到 6 v 的最短路为 1 2 5 6 v  v  v  v 路长 P(v6 )  7 。 事实上，在得到 1 v 到 6 v 的最短路 的同时，还得到了 1 v 到其它各点的最短路。 应该注意的是，本算法只适用全部权为非负的情况，如果某边上权为负的，此算法不 能使用。 [本讲小结] 今天我们学习了图的基本概念与基本定理、树与最小支撑数的概念及求最小树的算法、 最短通路问题及其 Dijkstra 算法，希望大家课下要很好的复习 v 1 v 2 v 3 v 4 v 6 v 5 3 5 2 2 4 2 4 2 图 8—14 1 （0） （3） （4） （5） （5） （7）