2011年广工成教离散数学复习题

一、 写出集合{a,b,c}的幂集。

参考答案：P(A) = { ?,{c},{b},{b,c},{a},{a,c},{a,b},{a,b,c}}

二、 设A={a，b，c}，B={0，1}，求A×P(B) （P(B)是B的幂集） 参考答案

A×P(B)={,,,,,,,, ,,, }

三、 70名学生参加体育比赛，短跑得奖者36人，弹跳得奖者29人，投掷得奖

者36人；三项都得奖者6人；仅得两项奖的有24人。求一项都没有得奖的人数。

参考答案：设R={短跑得奖者}；J={弹跳得奖者}；T={投掷得奖者}；

一项奖都没得的人数 = |~(R?J?T)| = |U|?| R?J?T |

根据容斥原理，|R?J?T| = |R|+|J|+|T|?|R?J |?|R ?T|?| J?T|+|R?J?T|

而仅得两项奖的人数 = (|R?J |?|R?J?T|)+(|R ?T|?|R?J?T|)+(| J?T|?|R?J?T|) = (|R?J |+|R ?T|+| J?T|)?3|R?J?T| 故|R?J |+|R ?T|+| J?T|=仅得两项奖的人数+3|R?J?T|

因此，|R?J?T| = |R|+|J|+|T|?(|R?J |+|R ?T|+| J?T|)+ |R?J?T| = |R|+|J|+|T|?仅得两项奖的人数?2|R?J?T| = 36+29+36?24?12=65

一项奖都没得的人数 = |~(R?J?T)| = |U|?| R?J?T |=70?65=5

四、 设 A={1,2,3,4,5,8}, 求R = { | x, y?A ? x?y(mod 3) }的商集A/R。 参考答案

[1]= {1,4} = [4],

[2] = {2,5,8} = [5] = [8] [3] = {3}.

A/R ={ {1,4}, {2,5,8}, {3} }.

五、 设A={a，b，c，d}，A上二元关系R={（a，b），（b，a），（c，a），（a，c），

（b，c），（c，b）}

（1）画出R的关系图。（2）求自反闭包r(R)

（3）R是否等价关系？如果是则求其等价类。

参考答案

（1）关系图

abcabcd

d (2) r(R)={ （a，a），（b，b），（c，c），（d，d），（a，b），（b，a），（c，a），（a，c），

（b，c），（c，b）}

(3)不是等价关系

六、 在边长为a的等边三角形内，任取7个点，证明其中必有3个点连成的小三

角形的面积不超过(3/12)a2。 参考答案

设等边三角形的三个顶点分别为a、b和c，g为该等边三角形的重心。边长为a的三角形

2的面积是：(3/4)a， ①

若7个点都在一条直线上，则任意三个点连成的图形面积都为0。命题得证。

若7个点不全在一条直线上，故根据鸽洞原理，至少有三个点落在gab、gac或gbc这三个三角形内部。②

不失一般性，设x、y和z三个点落在三角形gab中，则三角形xyz的面积?gab的面积

2=(3/12)a。 ③

故命题得证。

七、 证明：一个简单有向图G是强连通的 ? G中有一条包含所有顶点的基本回

路。 参考答案

? ： Ｇ中有一条包含所有顶点的基本回路，显然强连通。/*连通图的定义*/ ? ：如果 G强连通，G中的顶点为v1，v2，….vn, 设v1到v2路径为P1，v2到

v3的路径为P2 ，……， vn到v1 的路为Pn ，将P1， P2，…... Pn连起来，此路是一条长度为n基本回路。/*长度为n基本回路包含了n个不同的顶点*/

八、 用狄克斯特洛算法求下图中u到c的最短通路。

f 7 2 1 2 7 4 3 6 3 e 5 1 3 6

a

2 8 u4 0b g 4 d

c 参考答案

九、 写出集合{?,{?}}的幂集。 参考答案

?，{?}，{{?}}，{?,{?}}。

十、 画出4阶无向完全图K4的所有含有3条边的生成子图。 参考答案

G1G2G3

十一、 证明n阶有向完全图的边数为n2。 参考答案

设n阶有完全图的边数为m，则图中所有点的度数和为2m。

而n阶无向完全图的每个顶点都与其它顶点都有两条方向相反的边相连，并且有自回路，故图中每个点度数都为2(n-1)+2=2n。① 进而所有点的度数和为2n*n=2n2。② 因此2m=2n2，故m=n2。③

十二、 有向图G= V={v1,v2,v3,v4},

E={(v1,v2),(v2,v3),(v2,v4),(v3,v2),(v3,v4),(v3,v1), (v4,v1)}。 （i）画出图形。（ii）求邻接矩阵。 参考答案 (1)

v1v2 v3v4 (2) 邻接矩阵：

V1 V2 V3 V4 1 0 1 0 0 1 0 0 0 1 1 0 V1 0 V2 0 V3 1 V4 1

十三、 设G是n阶无向简单图，若G中任意不同的两个顶点的度数之和大于等

于n–1，试证明G是连通图。 参考答案

反证法。假设G不连通。

不妨设G有k个连通分支，n1，n2，……，nk是各分支的顶点数。显然有： n1 + n2 + nk = n ①

任取u ? G1, 则deg(u) <= n1 – 1 v ? G2, 则deg(v) <= n2 – 1

于是：deg(u)+deg(v)=n1–1+n2–1<=n–2 ②

与题设“任意不同的两个顶点的度数之和大于等于n–1”矛盾。 ? G是连通图 ③

十四、 证明：模K关系是任何整数集A上的等价关系。 参考答案

若A=? 则结论成立。若A不为?，则