试卷六试题与答案一、填空
1.任何(n,m) 图G = (V,E) , 边数与顶点度数的关系是。

2.当n为时,非平凡无向完全图K n是欧拉图。

3.已知一棵无向树T有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T中有个1度顶点。

二、选择
1、下面四组数能构成无向图的度数列的有( )。

A、 2,3,4,5,6,7；
B、 1,2,2,3,4；
C、 2,1,1,1,2；
D、 3,3,5,6,0。

2、图的邻接矩阵为( )。

A、
⎪⎪
⎪
⎪
⎪
⎭
⎫
⎝
⎛
1
1
1
1
1
1
1
；B、
⎪⎪
⎪
⎪
⎪
⎭
⎫
⎝
⎛
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
1
；C、
⎪⎪
⎪
⎪
⎪
⎭
⎫
⎝
⎛
1
1
1
1
1
1
1
；D、
⎪⎪
⎪
⎪
⎪
⎭
⎫
⎝
⎛
1
1
1
1
1
1
1。

3、下列几个图是简单图的有( )。

A.G1=(V1,E1), 其中 V1={a,b,c,d,e},E1={ab,be,eb,ae,de}；
B.G2=(V2,E2)其中V2=V1,E2={<a,b>,<b,c>,<c,a>,<a,d>,<d,a>,<d,e>}；
C.G=(V3,E3), 其中V3=V1,E3={ab,be,ed,cc}；
D.G=(V4,E4),其中V4=V1,E4={（a,a）,（a,b）,（b,c）,（e,c）,（e,d）}。

4、下列图中是欧拉图的有( )。

5、),2(⊕=S
G ，其中}3,2,1{=S ，⊕为集合对称差运算，
则方程}3,1{}2,1{=⊕x 的解为（ ）。

A 、}3,2{；
B 、}3,2,1{；
C 、}3,1{；
D 、Φ。

三、 证明
1、 若图G 中恰有两个奇数顶点，则这两个顶点是连通的。

2、 证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。

四、 根树的应用
在通讯中，八进制数字出现的频率如下：
0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5% 求传输它们最佳前缀码（写出求解过程）。

五、设B 4={e , a , b , ab }，运算*如下表，
则<B 4,*>是一个群（称作Klein 四元群）。

答 案
一、 填空 15%（每小题3分）
1、∑∈=V
v m
v d 2)(；2、奇数；3、5
二、 选择 15%（每小题 3分）
三、 证明
1、证：设G 中两个奇数度结点分别为u ，v 。

若 u ，v 不连通，即它们中无任何通路，则至少有两个连通分支G 1、G 2，使得u ，v 分别属于G 1和G 2。

于是G 1与G 2中各含有一个奇数度结点，与握手定理矛盾。

因而u ，v 必连通。

2、证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8 由图论基本定理知：
242)deg(=⨯=∑m F ，而3)deg(≥i
F ，所以必有
3)deg(=i F ，即每个面用3条边围成。

四、
根树的应用
解：用100乘各频率并由小到大排列得权数
30,20,15,10,10,5,5,587654321========w w w w w w w w
（1） 用Huffman 算法求最优二叉树：
（2） 前缀码
用 00000传送 5；00001传送 6；0001传送 7；100传送 3；101传送 4；001传送 2；11传送 1；01传送 0 （频率越高传送的前缀码越短）。

五、 10%
证明：
（1） 乘：由运算表可知运算*是封闭的。

（2） 群：即要证明)*(**)*(z y x z y x =，这里有43=64个等式需要验证
但：① e 是幺元，含e 的等式一定成立。

②ab=a*b=b*a ，如果对含a ，b 的等式成立，则对含a 、b 、ab 的等式也都成立。

③剩下只需验证含a 、b 等式，共有23=8个等式。

即：
(a*b)*a=ab*a=b=a*(b*a)=a*ab=b ； (a*b)*b=ab*b=a=a*(b*b)=a*e=a ；
(a*a)*a=e*a=a=a*(a*a)=a*e=a ；(a*a)*b=e*b=b=a*(a*b)=a*ab=b；
(b*b)*a=e*a=a=b*(b*a)=b*ab=a；(b*b)*b=e*b=b=b*(b*b)=b*e=b；
(b*a)*a=ab*a=b=b*(a*a)=b*e=b ；(b*a)*b=ab*b=a=b*(a*b)=b*ab=a 。

（3）幺：e为幺元
（4）逆：e -1=e ；a -1=a ；b -1=b ；(ab) -1=ab 。

所以<B4,*>为群。