离散数学
２、f和g都是群<G1 ,★>到< G2, *>的同态映射，证明<C , ★>是<G1, ★>的一个子
群。其中C={x|x G1且f(x) g(x)} (8分)
３、G=<V, E> (|V| = v，|E|=e ) 是每一个面至少由k（k 3）条边围成的连通平面
图，则
e
k(v 2)
k 2， 由此证明彼得森图（Peterson）图是非平面图。（11分）
四、逻辑推演 16%
用CP规则证明下题（每小题 8分） 1、A B C D,D E F A F 2、 x(P(x) Q(x)) xP(x) xQ(x)
五、计算 18%
1、设集合A={a，b，c，d}上的关系R={<a , b > ,< b , a > ,< b, c > , < c , d >}用矩阵运算求出R的传递闭包t (R)。 （9分）
2、如下图所示的赋权图表示某七个城市v1,v2, ,v7及预先算出它们之间的一些直接通信线路造价，试给出一个设计方案，使得各城市之间能够通信而且总造价最小。 （９分）
试卷一答案：
一、填空 20% （每小题2分）
1、{0，1，2，3，4，6}； 2、(B C) A；3、1； 4、( P S R) ( P S R)； 5、1；6、{<1,1>, <1,3>, <2,2>, <2,4> }；7、{<a.b>,<a,c>,<a,d>,<b,d>,<c,d>} IA ；8、
9、a ；a , b , c ,d ；a , d , c , d ；10、
c;