§63树及其应用.docVIP

§6.3 树 3.1 基本概念 连通的无圈图叫做树，记之为。若图满足，，则称是的生成树。图连通的充分必要条件为有生成树。一个连通图的生成树的个数很多，用表示的生成树的个数，则有公式 公式 Caylay 。 公式 。 其中表示从上删除边，表示把的长度收缩为零得到的图。 树有下面常用的五个充要条件。 定理1 （i）是树当且仅当中任二顶点之间有且仅有一条轨道。 （ii）是树当且仅当无圈，且。 （iii）是树当且仅当连通，且。 （iv）是树当且仅当连通，且，不连通。 （v）是树当且仅当无圈，，恰有一个圈。 3.2 应用—连线问题 欲修筑连接个城市的铁路，已知城与城之间的铁路造价为，设计一个线路图，使总造价最低。 连线问题的数学模型是在连通赋权图上求权最小的生成树。赋权图的具有最小权的生成树叫做最小生成树。 下面介绍构造最小生成树的两种常用算法。 prim算法构造最小生成树 设置两个集合和,其中用于存放的最小生成树中的顶点，集合存放的最小生成树中的边。令集合的初值为（假设构造最小生成树时，从顶点出发），集合的初值为。prim算法的思想是，从所有，的边中，选取具有最小权值的边，将顶点加入集合中，将边加入集合中，如此不断重复，直到时，最小生成树构造完毕，这时集合中包含了最小生成树的所有边。 prim算法如下： （i），； （ii）while end 例11 用prim算法求右图的最小生成树。 我们用的第一、二、三行分别表示生成树边的起点、终点、权集合。Matlab程序如下： clc;clear; M 1000; a 1,2 50; a 1,3 60; a 2,4 65; a 2,5 40; a 3,4 52;a 3,7 45; a 4,5 50; a 4,6 30;a 4,7 42; a 5,6 70; a [a;zeros 2,7 ]; a a+a;a find a 0 M; result [];p 1;tb 2:length a ; while length result ~ length a -1 temp a p,tb ;temp temp : ; d min temp ; [jb,kb] find a p,tb d ; j p jb 1 ;k tb kb 1 ; result [result,[j;k;d]];p [p,k];tb find tb k []; end result Kruskal算法构造最小生成树 科茹斯克尔（Kruskal）算法是一个好算法。Kruskal算法如下: i 选，使得。 ii 若已选好，则从中选取，使得 ① 中无圈，且 ② 。 iii 直到选得为止。 例12 用Kruskal算法构造例3的最小生成树。 我们用存放各边端点的信息，当选中某一边之后，就将此边对应的顶点序号中较大序号改记为此边的另一序号，同时把后面边中所有序号为的改记为。此方法的几何意义是：将序号的这个顶点收缩到顶点，顶点不复存在。后面继续寻查时，发现某边的两个顶点序号相同时，认为已被收缩掉，失去了被选取的资格。 Matlab程序如下： clc;clear; M 1000; a 1,2 50; a 1,3 60; a 2,4 65; a 2,5 40; a 3,4 52;a 3,7 45; a 4,5 50; a 4,6 30;a 4,7 42; a 5,6 70; [i,j] find a~ 0 a~ M ; b a find a~ 0 a~ M ; data [i;j;b];index data 1:2,: ; loop max size a -1; result []; while length result loop temp min data 3,: ; flag find data 3,: temp ; flag flag 1 ; v1 data 1,flag ;v2 data 2,flag ; if index 1,flag ~ index 2,flag result [result,data :,flag ]; end if v1 v2 index find index v1 v2; else index find index v2 v1; end data :,flag []; index :,flag []; end result