137682543176524316524315243152

4、求下列最小生成树的权值

12234

C(T)=1+2+3=6

31531

C(T)=1+2+3+1=7

24620232836814916153

C(T)=1+3+4+8+9+23=48

1718549761023

C(T)=1+2+3+5+7=18

617713863161712

C(T)=3+6+6+7=22

1687569613114

C(T)=4+5+6+7=22

v292v14510v5v336831012v77v4C(T)=2+3+4+5+6+10=30

11v6

1223410037

56C(T)=2+2+3+5+6+100=118

4879102081215

C(T)=8+9+4+7=28

1355736241

C(T)=1+3+3+2+1=10

125412585854971689716899

54145454153633623662

161139108211176453910827C(T)=1+2+3+5+7=1845

5、在右图所示的带权图中，共有多少棵生成树，他们的权各为多少？，其中哪些是图中的最小生成树？

a1b322d4ca31w=8412w=6bcbca31w=6b2adad1w=74124b2a3w=94b2da3dadw=824cb2cbda3cbdw=72w=72ccdc五、求最优二叉树

对给定的实数序列w1?w2?L?wt，构造最优r元树的递归算法：

1、求最优二元树的Huffman算法：第一步，连接以w1,w2为权的两片树叶，得一个分支点及其所带的权w1?w2；第二步，在w1?w2,w3,L,wt中选出两个最小的权，连接它们对应的结点（不一定都是树叶），又得分支结点及其所带的权；重复第二步，直到形成t?1个分支点，t片树叶为止。

t?1为整数，则求法与求最优二元树的r?1t?1Huffman算法类似，只是每次取r个最小的权；（2）若不为整数，得余数s?[1,r?1)，

r?1将s?1个较小的权对应的树叶为兄弟放在最长的路径上，然后算法同（1）。

2、求最优r?r?3?元树的Huffman算法：（1）若

1、找出叶的权分别为2，3，5，7，11，13，17，19，23，29，31，37，41的最优叶加权二叉树，并求其加权路径的长度。（

???w?v??L?v????789）

v?V29111323137411423753

172、求带权为2，3，5，7，8的最优二元树T，并给出T对应的二元前缀码集合。

（B={00,010,011,10,11},W(T)=2?5?3?2?3?3?2?7?2?8?55）

52378

3、求带权为1，2，3，4，5，6，7，8的最优二元树T，并给出T对应的二元前缀码集合。 （B={000,001,01000,01001,0101,011,10,11},W(T)=102）

7456312812578345623 4、（1）求带权为1，1，2，3，3，4，5，6，7的最优三元树；（2）求带权为1，1，2，3，3，4，5，6，7，8的最优三元树

3240201286456104311237157732211345

C(T1)=61,C(T2)=81

六、如图G

v2eafbv3cgdv5

v1v4图中的边割集有S1?{a,f,d},S2?{a,e,b},S3?{b,c,f},