离散数学习历年真题

7、下列函数是双射的为（ ）

A．f : I E , f (x) = 2x ； B．f : N N N, f (n) = <n , n+1> ； C．f : R I , f (x) = [x] ； D．f :I N, f (x) = | x | 。 （注：I—整数集，E—偶数集， N—自然数集，R—实数集） 8、图 中 从v1到v3长度为3 的通路有（ ）条。

A． 0； B． 1；

C． 2；

D． 3。

9、下图中既不是Eular图，也不是Hamilton图的图是（ ）

10、在一棵树中有7片树叶，3个3度结点，其余都是4度结点则该树有（ ）个4度结点。 A．1； B．2； C．3； D．4 。

三、证明 26%

１、R是集合X上的一个自反关系，求证：R是对称和传递的，当且仅当

< a, b> 和<a , c>在R中有<.b , c>在R中。（8分）

２、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）条边围成的连通平面图，则

此证明彼得森图（Peterson）图是非平面图。（11分）

e

k(v 2)

k 2， 由