lisan(2)-2-qm《离散数学(2)-2》复习材料
- 格式：doc
- 大小：1.42 MB
- 文档页数：5
《离散数学（2）-2》复习材料
一．选择题
1、由集合运算定义，下列各式正确的有（ A ）。
A.X ⊆X ⋃Y
B.X ⊇X ⋃Y
C.X ⊆X ⋂Y
D.Y ⊆X ⋂Y
2、设A B -=∅，则有 ( C )。
A ．
B =∅ B ．B ≠∅
C ．A B ⊆
D ．A B ⊇
3、对任意的集合A 、全集U ，下列命题为假的是( D )
A ．A ⋃∅ ＝A ， B. A ⋃U = U
C ．A ⋂∅ = ∅， D. A ⋂U = U
4、集合A={1，2，…，10}上的关系R={<x,y>|x+y=10,x ∈A,y ∈A },则R 的性质为(
B )。
A ．自反的
B ．对称的
C ．传递的，对称的
D ．反自反的，传递的
5、设R 和S 是集合A 上的任意关系，则下列命题为真的是 ( A )。
A ．若R 和S 是自反的，则R S 也是自反的
B ．若R 和S 是反自反的，则R S 也是反自反的
C ．若R 和S 是对称的，则R S 也是对称的
D ．若R 和S 是传递的，则R S 也是传递的
6、设R 和S 是非空集合A 上的等价关系，则下面是A 上的等价关系的是( D )。
A ．()A A R ⨯-
B ．S R ⋃
C ．S R -
D ．S R ⋂
7、设函数f ：N→N（N 为自然数集），f(n)=n+1，下面四个命题为真的是 ( A )
A. f 是单射
B. f 是满射
C. f 是双射的
D. f 非单射非满射
8、图G 和'G 的结点和边分别存在一一对应关系是G 和'G 同构的 ( B )。
A ．充分条件
B ．必要条件
C ．充要条件
D ．既不充分也不必要条件
9、平面图(如下)的三个面的次数分别是（ A ）
A ．11，3，4
B ．11，3，5
C ．12，3，6
D ．10，4，3
10、G 是连通平面图，有5个顶点．6个面，则G 的边数为（ D ）
A ．6
B ．5
C ．11
D ．9 二、证明题
1、设 A 为一有限集合，| A | = n ，那么 A 的子集个数为2n 。
证：A 有子集：没有元素的子集 ∅，计 0n C 个（ 0n C ＝1）; 恰含A 中一个元素的子集计
1n C 个,恰含A 中两个元素的子集计 2n C 个, … , 恰含A 中n 个元素的子集计 n n C 个。
因此A 的
子集个数为
0n C +1n C ＋…＋n n C =2n
2、设集合X={<1,2>, <3,4>, <5,6>,… }，R={<<x 1,y 1>,<x 2,y 2>>|x 1+y 2 = x 2+y 1} 。
证明R 是X 上的等价关系。
证明：
（1） 自反性：y x y x X y x +=+>∈<∀由于,,
自反R R y x y x >>∈<><<∴,,,
（2） 对称性：X y x X y x >∈<∀>∈<∀2211,,,
时当R y x y x >>∈<><<2211,,, 21121221y x y x y x y x +=++=+也即即
有对称性故R R y x y x >>∈<><<1122,,,
（3） 传递性：X y x X y x X y x >∈<∀>∈<∀>∈<∀332211,,,,
时且当R y x y x R y x y x >>∈<><<>>∈<><<33222211,,,,,,
⎩⎨⎧+=++=+)2()1(2
3321221y x y x y x y x 即 23123221)2()1(y x y x y x y x +++=++++
即1331y x y x +=+
有传递性故R R y x y x >>∈<><<3311,,,
由（1）（2）（3）知：R 是X 上的等价关系。
3. 设f 是A 到A 的满射，且f f f = ，证明f=I A 。
证明：因为f 是满射，所以A a ∈∀，存在A a ∈1使得a a f =)(1，又因为f 是函数，所以
)())((1a f a f f = 即)()(1a f a f f = 由 f f f =
所以)()(1a f a f =，又a a f =)(1，所以a a f =)( 由a 的任意性知：f=I A 。
4. 设G 为具有n 个结点的简单图，且)2)(1(2
1-->n n m 则G 是连通图。
反证法：若G 不连通，不妨设G 可分成两个连通分支G 1、G 2，假设G 1和G 2的顶点数分别为n 1和n 2，显然n n n =+21。
11112121-≤-≤∴≥≥n n n n n n
2
)2)(1(2)2)(1(2)1(2)1(212211--=-+-≤-+-≤∴n n n n n n n n n m 与假设矛盾。
所以G 连通。
5. 证明在6个结点12条边的连通平面简单图中， 每个面的面数都是3。
证：n=6,m=12 欧拉公式n-m+f=2知 f=2-n+m=2-6-12=8
由图论基本定理知：242)deg(=⨯=∑m F ，而3)d e g (≥i F ，
所以必有3)deg(=i F ，即每个面用3条边围成。
6. R 是集合X 上的一个自反关系，求证：R 是对称和传递的，当且仅当
< a, b> 和<a , c>在R 中有<.b , c>在R 中。
证：
“⇒” X c b a ∈∀,, 若R >c ,a <,>b ,a <∈ 由R 对称性知R a ,c <,>a ,b <∈>，由R 传递性得 R >c ,b <∈
“⇐” 若R >b ,a <∈，R >c ,a <∈ 有 R >c ,b <∈ 任意 X b a ∈,，因R >a ,a <∈ 若R >b ,a <∈ R >a ,b < ∈∴ 所以R 是对称的。
若R >b ,a <∈，R >c b,<∈ 则 R c b, R >a b,<>∈<∧∈
R >c ,a < ∈∴ 即R 是传递的。
7. 若图G 中恰有两个奇数度顶点，则这两个顶点是连通的。
证：设G 中两个奇数度结点分别为u ，v 。
若 u ，v 不连通则至少有两个连通分支G 1、G 2，使得u ，v 分别属于G 1和G 2。
于是G 1与G 2中各含有一个奇数度结点，与握手定理矛盾。
因而u ，v 必连通。
三、解答题
1. 设集合A={ a ,b , c , d }上关系R={< a, b > , < b , a > , < b , c > , < c , d >}
要求 （1）、写出R 的关系矩阵和关系图。
（2）、用矩阵运算求出R 的传递闭包。
解：（1）、⎪⎪⎪⎪
⎪⎭
⎫
⎝⎛=0000100001010010R M ； 关系图
（2）、⎪⎪⎪⎪
⎪⎭
⎫
⎝⎛==00000000101001012R R R M M M
⎪⎪⎪⎪
⎪⎭
⎫
⎝⎛==000000000101101023R R R M M M
2340000000010100101R R R R M M M M =⎪⎪⎪⎪
⎪⎭
⎫
⎝⎛== ,,4635R R R R M M M M ==
⎪⎪⎪⎪
⎪⎭
⎫
⎝⎛=+++=0000100011111111432)(R R R R R t M M M M M
∴ t (R)={<a , a> , <a , b> , < a , c> , <a , d > , <b , a > , < b ,b > , < b , c . > , < b , d > , < c , d > }。
2. 假设英文字母，a ，e ，h ，n ，p ，r ，w ，y 出现的频率分别为12%，8%，15%，7%，6%，10%，5%，10%，求传输它们的最佳前缀码，并给出happy new year 的编码信息。
解：
根据权数构造最优二叉树：
传输它们的最佳前缀码如上图所示，happy new year的编码信息为：
10 011 0101 0101 001 110 111 0100 001 111 011 000
附：最优二叉树求解过程如下：。
