内容发布更新时间 : 2026/7/19 9:11:21星期一 下面是文章的全部内容请认真阅读。
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
?1)时，结论成立，当k=t时, 无向图 G是t棵树组成的森林,任取两棵树，每棵树任取一个顶点，这两个顶点连线。则所得新图有t-1
棵树，所以m = n-（k-1）.
所以原图中m = n-k 得证。
24、在图所示2图中，实边所示的生成子图T是该图的生成树.
(1)指出T的弦，及每条弦对应的基本回路和对应T的基本回路系统.
(2) 指出T的所有树枝， 及每条树枝对应的基本割集和对应T的基本割集系统.
(a) (b) 图 解：(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、求图所示带权图中的最小生成树.
(a) (b)
图
解：
注：答案不唯一。
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算法求传输它们的前缀码.要求画出最优树，指出每个字母对应的编码.并指出传输10(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
传输10(n≥2)个按上述频率出现的字母，需要255*10个二进制数字
n
n-2
n