离散数学图论与关系中有图题目 下载本文

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},