最小树问题课件

第二节最小树问题

一、树的基本概念

在各种各样的图中，有一类图是十分简单又非常具有应用价值的图，这就是树。

例3已知有六个城市，它们之间要架设电话线，要求任意两个城市均可以互相通话，并且电话线的总长度最短。如果用六个点v1…v6代表这六个城市，在任意两个城市之间架设电话线，即在相应的两个点之间连一条边。这样，六个城市的一个电话网就作成一个图。任意两个城市之间均可以通话，这个图必须是连通图。并且，这个图必须是无圈的。否则，从圈上任意去掉一条边，剩下的图仍然是六个城市的一个电话网。图5-6是一个不含圈的连通图，代表了一个电话线网。一、树的基本概念

图5-6v6v3v4v2v5v1一、树的基本概念

无圈且连通的无向图称为树．树一般记为T．作为树定义还可以有以下几种表述：

(1)T连通且无圈或回路；(2)T无圈且有n－1条边（如果有n个结点）；(3)T连通有n－1条边；(4)T无回路，但不相邻的两个结点之间联以一边，恰得一个圈；(5)T连通，但去掉T的任意一条边，T就不连通了；（亦即，在点集合相同的图中，树是含边数最少的连通图。）(6)T的任意两个结点之间恰有一条初等链．

1．树一、树的基本概念

定义3

设图K=(V,EI)是图G=(V,E)的一支撑子图,如果图K=(V,EI)是一个树,那么称K是G的一个支撑树或生成树。

例如,图5-7b是图5-7a的一个支撑树。图5-7v6v5v2v3v4v1a2.支撑树v6v5v2v3v4v1b证明:必要性显然；充分性:设图G是连通的，若G不含圈，则按照定义，G是一个树，从而G是自身的一个支撑树。若G含圈，则任取G的一个圈，从该圈中任意去掉一条边，得到图G的一支撑子图G1。若G1不含圈，则G1是G的一个支撑树。若G1仍然含圈，则任取G1的一个圈，再从圈中任意去掉一条边，得到图G的一支撑子图G2。依此类推，可以得到图G的一个支撑子图GK，且不含圈，从而GK是一个支撑树。定理3一个图G有支撑树的充要条件是G是连通图。2.支撑树寻找连通图支撑树的方法有“破圈法”。就是从图中任取一个圈，去掉一条边。再对剩下的图重复以上步骤，直到不含圈时为止，这样就得到一个支撑树。例4用破圈法求出下图的一个支撑树。v5v4v2v3v1e6e5e4e3e2e1e7e8取一个圈(v1,v2,v3,v1)，在一个圈中去掉边e3

。在剩下的图中，再取一个圈（v1,v2,v4,v3,v1），去掉边e4

。再从圈（v3,v4,v5,v3）中去掉边e6

。再从圈(v1,v2,v5,v4,v3,v1）中去掉边e7，这样，剩下的图不含圈，于是得到一个支撑树，如图所示。2.支撑树v5v4v2v3v1e6e5e4e3e2e1e7e8v2e1e2e5e8v1v3v4v5破圈法任取一圈，从该圈中去掉任一条边对余下的圈重复相同的步骤直到将图中所有的圈都破掉为止避圈法也称为生长法从图中某一点开始生长边逐步扩展成长为一棵树每步选取与已入树的边不构成圈的那些边1．最小生成树二、最小生成树及其算法一个网络图可以有多个生成树．记N的所有生成树的集合为：

T＝{Tk|k＝1，2，…，L

}

设Tk

＝（V，Ek）是网络图N＝（G，w）的一棵生成树，则边集Ek中所有边的权数之和称为树Tk的权数，记为则称T*为网络N的一棵最小生成树，简称最小树．abfdec224256345最小树比如，城市间交通线的建造等，可以归结为这一类问题。再如前面例3，在已知的几个城市之间联结电话线网，要求总长度最短和总建设费用最少，这类问题的解决都可以归结为最小树问题。1．最小生成树(1)避圈法：从网络图中任意节点开始寻找与该节点关联的权数最小的边，使之与已选边不构成为圈，直到选够n-1条边为止。例最小树，权为13v14v21v31231v84v04v45245v73v62v515从网络中任选一点

2．最小树的求法求最小树的两种方法，是避圈法与破圈法v14v21v31231v84v04v45245v73v62v515(2)破圈法：①在网络图中寻找一个圈。若不存在圈，则已经得到最短树或网络不存在最短树；②去掉该圈中权数最大的边；反复重复①②两步，直到最小树。2．最小树的求法（3）Kruskal

算法：将图中所有边按权值从小到大排列，依次选所剩最小的边加入边集T，只要不和前面加入的边构成回路，直到T中有n1条边，则T是最小生成树v14v21v31231v84v04v45245v73v62v515图的矩阵表示将图的几何形状转化为代数矩阵形式，可大大方便计算机对图的处理与运算。1、无权图的矩阵表示：V5V4V3V2V1V1V2V3V4V5

V101100V210011V310001V401001V501110两顶点间有边连接的记为1，无边连接的记为0。得到的矩阵一定是对称矩阵。2、赋权无向图的矩阵表示：两顶点间有边连接的记为该边的权数。无边相连的记为，对角线上的数是0。得到的矩阵也是对称矩阵。例如：V1V2V3V4V5

V1032V23054V3208V4502V54820V5V4V38V25V123423、赋权有向图的矩阵表示：左边的第一列为弧的起点，在每一行中，以该点为起点，按弧的方向，依次填上到各点的权数。如没有到该点的弧，记为，对角线上的数是0。这样得到的矩阵不一定是对称矩阵。例如：起点V1V2V3V4V5

V1032V2054V3608V402V50终点V5V4V38V25V123426（4）Prim算法：不需要对边权排序，即可以直接在网路图上操作，也可以在边权矩阵上操作，后者适合计算机运算

边权矩阵上的Prim算法：1、根据网路写出边权矩阵，两点间若没有边，则用表示；2、从v1开始标记，在第一行打，划去第一列；3、从所有打的行中找出尚未划掉的最小元素，对该元素画圈，划掉该元素所在列，与该列数对应的行打；4、若所有列都划掉，则已找到最小生成树(所有画圈元素所对应的边)；否则，返回第3步。该算法中，打行对应的节点在V1中，未划去的列在V2中

最小生成树Prim算法是多项式算法Prim算法可以求最大生成树网路的边权可以有多种解释，如效率次数受限的最小生成树—尚无有效算法最小Steiner树—尚无有效算法练习如图S,A,B,C,D,E,T代表村镇,村镇之间的连线上赋予了权值(可代表距离,费用,流量等)现沿图中连线架设电线,使各村镇全部通电,问如何架设使电线总长最短.(该图称为赋权图或无向网络).最小生成树总长=2+2+1+3+1+5=14第三节最短路径问题

最短路径问题是图论中十分重要的最优化问题之一，它作为一个经常被用到的基本工具，可以解决生产实际中的许多问题，比如城市中的管道铺设，线路安排，工厂布局，设备更新等等。也可以用于解决其它的最优化问题。

例5如下图所示的单行线交通网，每个弧旁边的数字表示这条单行线的长度。现在有一个人要从v1出发，经过这个交通网到达v6，要寻求总路程最短的线路。v6v5v3v1v4v2365112436第三节最短路径问题

从v1到v6的路线是很多的。比如从v1出发，经过v2,v4到达v6或者从v1出发，经过v2，v3，v5到达v6等等。但不同的路线，经过的总长度是不同的。例如，按照第一个线路，总长度是3+6+3=12单位，按照第二个路线，总长度是3+1+1+6=11单位。第三节最短路径问题

第三节最短路径问题

一、基本概念给定一个赋权有向图D＝(V，A),对每一条弧aij＝w(vi，vj)，相应地有权w(aij)=wij，又有两点vs、vt∈V,设p是D中从vs到vt的一条路，路p的权是p中所有弧的权之和,记为w(p)．最短路问题就是求从vs到vt的路中一条权最小的路p*:第三节最短路径问题

下面仅介绍在一个赋权有向图中寻求最短路的方法——双标号法（Dijkstra算法），它是在1959年提出来的。目前公认，在所有的权wij

≥0时，这个算法是寻求最短路问题最好的算法。并且，这个算法实际上也给出了寻求从一个始定点vs到任意一个点vj的最短路。二、最短路问题的算法

6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)计算两节点之间或一个节点到所有节点之间的最短路令dij

表示vi

vj的直接距离(两点之间有边)，若两点之间没有边，则令dij

=，若两点之间是有向边，则dji

=；令dii

=0，s表示始点，t表示终点0、令始点Ts=0，并用（）框住，所有其它节点临时标记Tj=；1、从vs出发，对其相邻节点vj1进行临时标记，有Tj1=ds,j1；2、在所有临时标记中找出最小者，并用框住，设其为vr。若此时全部节点都永久标记，算法结束；否则到下一步；3、从新的永久标记节点vr出发，对其相邻的临时标记节点进行再标记，设vj2为其相邻节点，则Tj2=min{Tj2,Tr+dr,j2}，返回第2步。6.3.1狄克斯特拉算法(Dijkstraalgorithm,1959)计算两节点之间或一个节点到所有节点之间的最短路令dij

表示vi

vj的直接距离(两点之间有边)，若两点之间没有边，则令dij

=，若两点之间是有向边，则dji=；令dii

=0，s表示始点，t表示终点对每个节点，用两种标号：T和P，表示从始点到该节点的距离，P是最短距离(权)，为永久标号，T是目前路径的距离，是临时标号。通过不断改进T值，当其最小时，将其改为P标号。开始时，令始点有P=0的P标号，其它节点为T=+.标号过程分为两步：1.修改T标号。假定是新产生的P标号点，考察以为始点的所有弧段，如果是P标号点，则对该点不再进行标号；如果是T标号点，则进行如下修改2.产生新的P标号点，原则：在现有的所有T标号中将值最小者改为P标号二、最短路问题的算法

例6求v1到v6的最短路。+∞+∞+∞+∞+∞（1）首先给v1以P标号，P(v1)＝0，给其余所有点T标号，T(vj)＝＋∞（j=2，3，…6)(0)P标号以（）形式标在结点旁边，T标号以不带（）的数字标在结点旁边.v6v5v3v1v4v2365112436二、最短路问题的算法

P(v2)=3

（3）5P(v3)=4

（4）+∞+∞v6v5v3v1v4v2365112436+∞+∞+∞(0)9（2）考察v1:

T(v2)=min[T(v2)，P(v1)+d12]＝min[∞，0＋3]=3T(v3)=min[T(v3)，P(v1)+d13]＝min[∞，0＋5]=5所以，P(v2)=3（3）考察v2:T(v3)=min[T(v3)，P(v2)+d23]＝min[5，3＋1]=4T(v4)=min[T(v4)，P(v2)+d24]＝min[∞，3＋6]=9所以，P(v3)=4T(v3)=5

T(v4)=9

二、最短路问题的算法

P(v5)=5（3）（4）v6v5v3v1v4v2365112436+∞+∞(0)9（5）T(v4)=8

（4）考察v3:

T(v5)=min[T(v5)，P(v3)+a35]＝min[∞，4＋1]=5T(v4)=min[T(v4)，P(v3)+a34]＝min[9，4＋4]=8所以，P(v5)=5（5）考察v5:T(v6)=min[T(v6)，P(v5)+a56]＝min[∞，5＋6]=11T(v4)=min[T(v4)，P(v5)+a54]＝min[8，5＋2]=7所以，P(v4)=7

8T(v6)=11

11（7）P(v4)=7

二、最短路问题的算法

（3）（4）v6v5v3v1v4v236511243611(0)（5）（7）（6）考察v4:T(v6)=min[T(v6)，P(v4)+a46]＝min[11，7＋3]=10所以，P(v6)=10所有点都标上P标号．

P(v6)=10(10)(7)标出最短路v1到v6的最短路可从v1开始，根据永久性标号数值回溯得到．(7)标出最短路最短路径是：v1→v2→v3→v5→v4→v6，路长10．同时得到，到其余各点的最短路，即各点的永久性标号P（vi）．

注意：双标号法只适用于所有wij

≥0的情形，当赋权有向图中存在负权时，则算法失效．

（3）（4）v6v5v3v1v4v2365112436(0)（5）（7）(10)二、最短路问题的算法

例6.1设有一批货物要从v1运到v7，求最短运输路线。解：v1v2v3v5v6v7142157326

v4420,V2(1)v1v2v3v5v6v7142157326

v44201,V3(3)v1v2v3v5v6v7142157326

v442013,V6(4)v1v2v3v5v6v7142157326

v4420134,V4(5)v1v2v3v5v6v7142157326

v44201345,V5(7)v1v2v3v5v6v7142157326

v442013457,V7(9)v1v2v3v5v6v7142157326

v4420134579得最短路：V1V2V4V5V7：V1V2V3V6V5V7

例6.2设有一批货物要从v1运到v7，求最短运输路线。解：v1v2v3v5v6v7142157326v442二、最短路的矩阵算法解：先将图表示为矩阵形式。v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2102475V34201V4402V572032V651306V7260第一步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2102475V34201V4402V572032V651306V7260112+14+17+15+13586第二步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34201V4402V572032V651306V7260111+3433第三步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4402V572032V651306V7260113+4733446+410第四步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4402V572032V6517010V7260112+57334455第五步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572032V6517010V7260112+79334455777第六步：v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572039V6517010V7260112+7933445577799v1v2v3v5v6v7142157326v4420V1V2V3V4V5V6V7

V1014V2103586V34204V4407V572039V6