《最小生成树课件》由会员分享，可在线阅读，更多相关《最小生成树课件（32页珍藏版）》请在金锄头文库上搜索。
1、3最小生成树及算法,1) 树(tree)的定义与树的特征,定义 连通且不含圈的无向图称为树常用T表示.,树中的边称为树枝. 树中度为1的顶点称为树叶.,孤立顶点称为平凡树.,平凡树,注意：无向图,例如，图 6.4.1 给出的 G1 和 G2 是树，但G3 （有圈）和 G4 （不连通）则不是树。,G1 G2 G3 G4 图 6.4.1,定理2 设G是具有n个顶点的图，则下述命题等价：,1) G是树（ G无圈且连通）；,2) G无圈，且有n-1条边；,3) G连通，且有n-1条边；,4) G无圈，但添加任一条新边恰好产生一个圈;,5) G连通，且删去一条边就不连通了（即G为最,最小连通图）；,6)
2、 G中任意两顶点间有唯一一条路.,2）图的生成树(或支撑树 Spanning Tree),定义 若T是包含图G的全部顶点的子图,它又是树,则称T是G的生成树. 图G中不在生成树的边叫做弦.,定理3 图G=(V,E)有生成树的充要条件是图G是连,通的.,证明 必要性是显然的.,连通图得到生成,一般来讲，一个图的生成树不唯一。例如，在图6.4.2 中，(a)、(b)、(c) 均是 (d) 的生成树。,(c) (d) 图 6.4.2,(a) (b),（II）找图中生成树的方法,可分为两种：避圈法和破圈法,A 避圈法 : 深探法和广探法,B 破圈法,A 避圈法,定理3的充分性的证明提供了一种构造图的生
3、,成树的方法.,这种方法就是在已给的图G中，每步选出一条边使它与已选边不构成圈，直到选够n-1条边为止. 这种方法可称为“避圈法”或“加边法”,在避圈法中，按照边的选法不同，找图中生成树的方法可分为两种：深探法和广探法.,a) 深探法,若这样的边的另一端均已有标号，就退到标号为,步骤如下：,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给以标号0. 令i=0,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法求出下图10的一棵生成树,0
4、,1,2,3,4,5,6,7,8,9,10,11,12,13,13,a) 深探法,0,1,2,3,4,5,6,7,8,9,10,11,12,步骤如下：,若这样的边的另一端均已有标号，就退到标号为,i) 在点集V中任取一点u,ii) 若某点v已得标号，检,端是否均已标号.,若有边vw之w未标号,则给,w代v，重复ii).,i-1的r点,以r代v,重复ii),直到全部点得到标号为止.,给u以标号0.,查一端点为v的各边，另一,w以标号i+1，记下边vw.令,例用深探法求出下图10的一棵生成树,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的点集为,是否均已标号. 对所
5、有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0. 令i=0.,Vi,检查Vi,VVi中的边端点,边.,例用广探法求出下图10的一棵生成树,1,0,1,2,2,1,3,2,1,2,2,3,4,标号为止.,3,b)广探法,步骤如下：,i) 在点集V中任取一点u,ii) 令所有标号i的点集为,是否均已标号. 对所有未标,号之点均标以i+1,记下这些,iii) 对标号i+1的点重复步,步骤ii)，直到全部点得到,给u以标号0.令i=0.,Vi,检查Vi,VVi中的边端点,边.,例用广探法求出下图10的一棵生成树,1,0,1,2,2,1,
6、3,2,1,2,2,3,4,标号为止.,显然图10的生成树 不唯一.,B 破圈法,相对于避圈法，还有一种求生成树的方法叫做“破圈法”. 这种方法就是在图G中任取一个圈，任意舍弃一条边，将这个圈破掉，重复这个步骤直到图G中没有圈为止.,例 用破圈法求出,下图的一棵生成树.,B 破圈法,例 用破圈法求出下图的另一棵生成树.,不难发现，图的生成树不是唯一的 .,3) 最小生成树(Minimum Spanning Tree)与算法,介绍最小生成树（MST）的三种算法： 避圈法（ Kruskal算法和Prim算法）和破圈法.,A Kruskal算法（或避圈法）,思路如下：,1) 选择边e1，使得w(e1
7、)尽可能小；,2) 若已选定边 ，则从,中选取 ，使得:,i) 为无圈图，,ii) 是满足i)的尽可能小的权，,3) 当第2)步不能继续执行时，则停止.,定理4 由Kruskal算法构作的任何生成树,都是最小树.,Kruskal算法步骤,(1) 对属于E的边进行排序得,(2) 初始化操作,（3）若t=n-1,则转（6），否则转（4）,（4）若,（6）输出T，w，停止,例10用Kruskal算法求下图的最小树.,在左图中 权值,最小的边有 任取一条,在 中选取权值,最小的边,中权值最小边有 , 从中选,任取一条边,会与已选边构成圈,故停止,得,中选取在中选取,中选取 . 但 与 都,最小生成树的
8、Prim算法,Prim算法思路 从任意一顶点开始，首先把这个顶点包括在生成树里，然后在那些其一端已在生成树里，而另一端还未在生成树里的边中，找权值最小的一条边，并把这条边和其不在生成树里的那个顶点包括进生成树中。如此进行下去，每次往生成树里加入一个顶点和一条权最小的边，直到把所有顶点都包括进生成树里 理论上，当有两条具有相同最小权值的边可选择时，选哪一条都行，因此构造的最小生成树不一定唯一。但若给定算法，则唯一,Prim 算法的参考步骤 第一步 T0，w(T0)0，V v0。 第二步 对每一个点 vV V ，L(v)w(v, v0)（如果 (v, v0)E，则 w(v, v0) = ）。 第三
9、步 如果 V = V，输出 T0，w(T0)，停止。否则进行下一步。 第四步 在 V V 中找一点 u，使 L(u) = minL(v) | vV V ， 并将 V 中与 u 邻接的点记为 x，e = (x, u)。 第五步 T0T0e，w(T0)w(T0)+w(e)， V V u。 第六步 对所有 vVV ，如 w(v, u) L(v)，则 L(v) w(v, u)，否则 L(v) 不变。 第七步 转第三步。,从顶点a开始,结果显示于,图,最小生成树的 Kruskal 算法是 1956 年由Kruskal 提出的。随后在 1957 年，领导贝尔实验室数学研究室的 Prim 创立了他的算法。,
10、Kruskal 算法的时间复杂性以 O(mlog2m) 为界，当边数较多或是一个完全图时，m (n 1)2，则时间复杂性近似于 O(n2log2n)。而 Prim 算法的时间复杂性为O(n2)，所以，如果图的连通度较高（最高为完全图），以 Prim 算法较好，如果图的连通度较低，特别当 m O(n) 时，则 Kruskal 算法更合适。 在实际应用中，还会遇到求一个赋权图的最大生成树的问题。比如，某图的边权代表的是利润或效益，则最终的问题很可能就是求其最大生成树。事实上，从上面两个算法可以看出，只要边权的选择改为从大到小，求最小生成树的算就可以用来求最大生成树了。,令m表示边数,B破圈法,算法
11、2 步骤如下：,1) 从图G中任选一棵树T1.,2) 加上一条弦e1，T1+e1中,立即生成一个圈. 去掉此,圈中最大权边，得到新,树T2,以T2代T1,重复2)再,检查剩余的弦，直到全,部弦检查完毕为止.,例11用破圈法求下图的最小树.,先求出上图的一棵生成树.,加以弦 e2,得到的圈v1v3v2v1,去掉最大的权边e2,得到一棵新,树仍是原来的树；,再加上弦e7，得到圈 v4v5v2v4,去掉最大的权边e6，得到一棵,新树；如此重复进行，直到全,全部的弦均已试过,得最小树.,应用连线问题,欲修筑连接个城市的铁路，已知城与城之间的铁路造价为，设计一个线路图，使总造价最低。 连线问题的数学模型
12、是在连通赋权图上求权最小的生成树。,分组技术。分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工都在组内完成。 假设有 13 种零件，需在 9 台机器上加工。在各台机器上加工的零件号在下表中给出。 将这 9 台机器分为 3 组，使零件跨组加工的情形尽量少。,应用范例,解：(1) 建模 设用 Mi 表示需由机器 i 加工的零件集合。对任意两台机器 i，j，定义 i 与 j的相异度： 其中“”表示对称差，分子即为在机器 i 但不在机器 j 上加工，或在机器 j 但不在机器 i 上加工的零件数。分母为在机器
13、i 或在机器 j 上加工的零件数。显然，0 w 1，w(i, j) = 0 表示机器 i 与机器 j 加工的零件完全相同；w(i, j) = 1 表示机器 i 与机器 j 加工的零件没有一个相同。w 表达了两台不同机器加工零件的相异程度。,以机器为顶点，作一个完全图，每条边 (i, j) 被赋予权 w(i, j)。这个图的最小生成树是由那些相异度最小的边构成的连通图，或看成是去掉了相异度相对比较大的边后余下的连通图。如果希望把机器分成 k 个组，就继续删去最小生成树上权最大的 k1条边。于是得到 k 个分离的子树，每棵树的顶点就构成各机器组。 (2) 模型求解 对前面表中给出的数据，按照上述建模方式构造加权图，边权矩阵如下表所示。,用 Kruskal 算法可求出最小生成树，如下图。 将最小生成树中最大权的两条边去掉，得到三个分离树，它们的顶点集合分别为：3, 9，1, 2, 5，4, 6, 7, 8，这也就是机器的分组。,
