必须先下载后，才可以看到答案。

第十六章部分课后习题参

1、画出所有5阶和7阶非同构的无向树.

2、一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，问T有几个顶点?

解：设3度分支点个，则

     ，解得

T有11个顶点

3、无向树T有8个树叶，2个3度分支点，其余的分支点都是4度顶点，问T有几个4度分支点？根据T的度数列，请至少画出4棵非同构的无向树。

解：设4度分支点个，则

     ，解得

度数列111111113344

4、棵无向树T有(i=2，3，…，k)个i度分支点，其余顶点都是树叶，问T应该有几片树叶?

解：设树叶片，则

     ，解得

评论：2，3，4题都是用了两个结论,一是握手定理，二是

5、n(n≥3)阶无向树T的最大度至少为几？最多为几？

解：2，n-1

6、若n(n≥3)阶无向树T的最大度 =2，问T中最长的路径长度为几？

解：n-1

7、证明：n(n≥2) 阶无向树不是欧拉图.

证明：无向树没有回路，因而不是欧拉图。

8、证明：n(n≥2) 阶无向树不是哈密顿图.

证明：无向树没有回路，因而不是哈密顿图。

9、证明：任何无向树T都是二部图.

证明：无向树没有回路，因而不存在技术长度的圈，是二部图。

10、什么样的无向树T既是欧拉图，又是哈密顿图?

解：一阶无向树

14、设e为无向连通图G中的一条边， e在G的任何生成树中，问e应有什么性质?

解：e是桥

15、设e为无向连通图G中的一条边， e不在G的任何生成树中， 问e应有什么性质?

解：e是环                     

23、已知n阶m条的无向图 G是k(k≥2)棵树组成的森林，证明：m = n-k.；

证明：数学归纳法。k=1时, m = n-1，结论成立；

设k=t-1(t-1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1棵树，所以m = n-（k-1）.

所以原图中m = n-k

得证。

24、在图16.6所示2图中，实边所示的生成子图T是该图的生成树.

 (1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.

(2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统.

                (a)                             (b)

                           图16.16 

解：(a)T的弦：c,d,g,h

T的基本回路系统: S={{a,c,b},{a,b,f,d},{e,a,b,h},{e,a,b,f,g}}

T的所有树枝: e,a,b,f

T的基本割集系统: S={{e,g,h},{a,c,d,g,h},{b,c,d,g,h},{f,d,g}}

(b)有关问题仿照给出

25、求图16.17所示带权图中的最小生成树.

(a)                       (b)

图16.17

解：

注：答案不唯一。

37、画一棵权为3，4，5，6，7，8，9的最优2叉树，并计算出它的权.

38.下面给出的各符号串集合哪些是前缀码?

      A1={0，10，110，1111}   是前缀码

      A2={1，01，001，000}    是前缀码

      A3={1，11，101，001，0011}   不是前缀码

      A4={b，c，aa，ac，aba，abb，abc}      是前缀码

      A5={ b，c，a，aa，ac，abc，abb，aba}   不是前缀码

41.设7个字母在通信中出现的频率如下:

                a: 35%               b: 20%

                c: 15%               d: 10%

                e: 10%               f: 5%

                g: 5%

用Huffman算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10n(n≥2)个按上述频率出现的字母，需要多少个二进制数字.

解：

a:01  b:10  c:000  d:110  e:001  f:1111  g:1110

W(T)=5*4+5*4+10*3+10*3+15*3+20*2+35*2=255

传输10n(n≥2)个按上述频率出现的字母，需要255*10n-2个二进制数字.下载本文