Primf及Krusf最小成树及matlab源代码

1、1,五 树与生成树,树是一种特殊的图, 它是图论中重要的概念之一, 它有 着广泛的应用.在计算机科学中有如判定树、语法树、分 类树、搜索树、目录树等等. 一.树 (Tree) 1.树的定义:一个连通无回路的 无向图T,称之为树. 如(a),4.森林:一个无向图的每个连通分支都是树.如(b),2.叶结点:度数为1的结点, 称为叶结点. 3.分支结点(内结点):度数大于1的结点.,2,5.与树定义等价的几个命题 定理给定图T, 以下关于树的定义是等价的。 无回路的连通图。 无回路且e=v-1 其中e是T的边数,v是T的结点数。 连通的且e=v-1。 无回路但添加一条新边则得到一条仅有的回路。 连通

2、的,但删去任一条边,T便不连通。 每对结点之间有一条且仅有一条路。,3,二. 生成树(支撑树) 在图论的应用中,找出一个连通图的所有不同的生成树,以及找出最小生成树是很有意义的. 1.定义:如果图G的生成子图是树,则称此树为G的生成树. 2.弦:图G中,不在其生成树里的边,称作弦. 所有弦的集合,称为该生成树的补. 定理 连通图至少有一棵生成树.,4,三.赋权图的最小生成树 1.定义:一棵生成树中的所有边的权之和称为该生成树的 权. 具有最小权的生成树,称为最小生成树. 最小生成树很有实际应用价值.例如结点是城市名,边的权 表示两个城市间的距离, 从一个城市出发走遍各个城市, 如何选择最优的旅

3、行路线.又如城市间的通信网络问题,如 何布线,使得总的线路长度最短. 例如:右图所示 2.求最小生成树算法 -Kruskal算法: (避圈法),5,Kruskal 算法 思想：在不形成圈得条件下，优先挑选权小的边形成生成树。,数学建模-图论,四、最小生成树问题及其算法,6,注：算法构造的最小生成树的边集为 E1；标号 l 具有性质：当且仅当 u、v 之间有一条仅由 E1 中的边形成的路时，l(u) = l(v)，因此在步骤 (2) 发现 l(u) = l(v) 时，(u, v) 不能放入 E1，否则会形成一个圈。,数学建模-图论,四、最小生成树问题及其算法,7,例：利用Kruskal算法求出如

4、图G的最小生成树：,四、最小生成树问题及其算法,数学建模-图论,8,8,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,9,9,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,10,10,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,运行结果如下： T = 1 3 5 1 6 3 2 6 6 6 7 4 c = 26,上述例题的matlab程序如下： b=1 1 2 2 3 3 3 4 5 5 6;2 6 3 6 4 6 7 7 6 7 7;2 4 4 5 8 3 7 8 3 7 6; Krusf(b,1);,11,11,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,12,例 、一个乡有7个自然村，其间道路如图所示，要以村为中心建有线广播网络，如要求沿道路架设广播线，应如何架设？,a,b,c,d,e,g,f,14,18,27,16,8,21,3,a,e,12,d,c,b,7,g,f,19,5,13,13,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,14,14,2020年6月27日,四、最小生成树问题及其算法,数学建模-图论,15,15,2020年6月27日