一、 填空
1. 任何(n,m) 图G = (V,E) , 边数与顶点度数的关系是 。
2. 当n 为 时,非平凡无向完全图K n 是欧拉图。
3. 已知一棵无向树T 有三个3顶点,一个2度顶点,其余的都是1度顶点,
则T 中有 个1度顶点。 4．设}3,34,2,2,1{,
}
4,3,2,1{><><><==，R X ，则
r (R) = ；
s (R) = ； t (R) = 。
5．设R 为集合A 上的等价关系，对A a ∈∀，集合R a ][= ，称为元素a 形成的R 等价类，Φ≠R a ][，因为 。
6．任意两个不同小项的合取为 ，全体小项的析取式为 。 7．设为偶数
x x Q :)(，为素数
x x P :)(，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：
（1） ；
（2） 。
8．含5个结点，4条边的无向连通图（不同构）有 个，
它们是 。 9. 设T 为根树，若 ，则称T 为m 元树；
若 则称T 为完全m 叉树。
二、 选择
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 、⎪⎪⎪
⎪⎪⎭⎫ ⎝⎛00
1
101110100001
；B 、⎪⎪⎪
⎪⎪⎭⎫ ⎝⎛111111111111
1111；C 、⎪⎪⎪
⎪⎪⎭⎫
⎝⎛00
1
10111100
0010
；D 、⎪⎪⎪⎪⎪⎭⎫
⎝⎛00
1
10111010
0010
。
3、下列几个图是简单图的有( )。
A. G 1=(V 1,E 1), 其中 V 1={a,b,c,d,e},E 1={ab,be,eb,ae,de}；
B. G 2=(V 2,E 2)其中V 2=V 1,E 2={,,,,,}；
C. G=(V 3,E 3), 其中V 3=V 1,E 3={ab,be,ed,cc}；
D. G=(V 4,E 4),其中V 4=V 1,E 4={（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 、Φ。
三、判断改正题：（每小题2分，本大题共20分）
1．命题公式B B A A →→∧))((是一个矛盾式。 （ ） 2．任何循环群必定是阿贝尔群，反之亦真。 （ ） 3．根树中最长路径的端点都是叶子。 （ ） 4．若集合A 上的关系R 是对称的，则1
-R
也是对称的。 （ ）
5．数集合上的不等关系（≠）可确定A 的一个划分。 （ ） 6．设集合A 、B 、C 为任意集合，若A×B = A×C ，则B = C 。 （ ） 7．函数的复合运算“。”满足结合律。 （ ） 8．若G 是欧拉图，则其边数e 合结点数v 的奇偶性不能相反。 （ ） 9．图G 为（n , m ）图，G 的生成树
G T 必有n 个结点。 （ ）
10．使命题公式)(R Q P ∨→的真值为F 的真值指派的P 、Q 、R 值分别是T 、F 、F 。 （ ） 四.证明
1、若图G 中恰有两个奇数顶点，则这两个顶点是连通的。
2、证明：在6个结点12条边的连通平面简单图中，每个面的面度都是3。
3、某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由） 五.根树的应用
在通讯中，八进制数字出现的频率如下：
0：30%、1：20%、2：15% 、3：10%、4：10%、5：5%、6：5%、7：5% 求传输它们最佳前缀码（写出求解过程）。
六.设B 4={e , a , b , ab }，运算*如下表，
则是一个群（称作Klein 四元群）。
答 案
一、填空 15%（每小题3分）
1、∑∈=V
v m
v d 2)(； 2、奇数； 3、5
4．}4,4,2,2,1,1,3,3,4,2,2,1{)(><><><><><><=R r ， }2,4,1,2,3,3,4,2,2,1{)(><><><><><=R s ， }3,3,4,1{2
><><==R R R ， }3,3{2
3
><==R R R
，}3,3{3
4
><==R R R
，
所以， }4,1,3,3,4,2,2,1{)(><><><><=R t 。
5．
}
,{][aRx A x x a R ∈=；R a a ][∈。
6．永假式（矛盾式），永真式（重言式）。
7．（1）)))()(())()(((y x y P y Q y x P x Q x =→∧∃∧∧∃。 （2）))()()()((y x y P y Q x P x Q y x =→∧∧∧∀∀。 8．3。
9．每个结点的出度都小于等于m ；除叶子外，每个结点的出度都等于m 。
二.、选择 15%（每小题 3分）
1．× 命题公式B B A A →→∧))((是一个重言式。 2．× 任何循环群必定是阿贝尔群，但反之不真。 3．× 根树中最长路径的端点不都是叶子。
4．√ 5．× ≠不能确定A 的一个划分。 6．√ 7．√
8．× 欧拉图其边数e 和结点数v 的奇偶性可以相反。 9．√ 10．√
四、证明
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。由图论基本定理知：
