离散数学习题集(十五套)(4)

离散数学

２、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;

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说综合文库离散数学习题集(十五套)(4)在线全文阅读。