资源描述：
《2011年广工成教离散数学复习题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、一、写出集合{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人；
2、仅得两项奖的有24人。求一项都没有得奖的人数。参考答案：设R={短跑得奖者}；J={弹跳得奖者}；T={投掷得奖者}；一项奖都没得的人数=
3、~(RÈJÈT)
4、=
5、U
6、-
7、RÈJÈT
8、根据容斥原理，
9、RÈJÈT
10、=
11、R
12、+
13、J
14、+
15、T
16、-
17、RÇJ
18、-
19、RÇT
20、-
21、JÇT
22、+
23、RÇJÇT
24、而仅得两项奖的人数=(
25、RÇJ
26、-
27、RÇJÇT
28、)+(
29、RÇT
30、-
31、RÇJÇT
32、)+(
33、JÇT
34、-
35、RÇJÇT
36、)=(
37、RÇJ
38、+
39、RÇT
40、+
41、JÇT
42、)-3
43、RÇJÇT
44、故
45、RÇJ
46、+
47、RÇT
48、+
49、JÇT
50、=仅得两项奖的人数+3
51、RÇJÇT
52、
53、因此，
54、RÈJÈT
55、=
56、R
57、+
58、J
59、+
60、T
61、-(
62、RÇJ
63、+
64、RÇT
65、+
66、JÇT
67、)+
68、RÇJÇT
69、=
70、R
71、+
72、J
73、+
74、T
75、-仅得两项奖的人数-2
76、RÇJÇT
77、=36+29+36-24-12=65一项奖都没得的人数=
78、~(RÈJÈT)
79、=
80、U
81、-
82、RÈJÈT
83、=70-65=5四、设A={1,2,3,4,5,8},求R={
84、x,yÎAÙxºy(mod3)}的商集A/R。参考答案[1]={1,4}=[4],[2]={2,5,8}=[5]=[8][3]={3}.A/R={{1,4},{2,5,8},{3}}.五、设A={
85、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）关系图(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个点连成的小三角形的面积不超过。参考答案设等边三角形的三个顶点分别为a、b和c，g为该等边三角形的重心
86、。边长为a的三角形的面积是：，①若7个点都在一条直线上，则任意三个点连成的图形面积都为0。命题得证。若7个点不全在一条直线上，故根据鸽洞原理，至少有三个点落在gab、gac或gbc这三个三角形内部。②不失一般性，设x、y和z三个点落在三角形gab中，则三角形xyz的面积£gab的面积=。③故命题得证。二、证明：一个简单有向图G是强连通的ÛG中有一条包含所有顶点的基本回路。参考答案Ü：Ｇ中有一条包含所有顶点的基本回路，显然强连通。/*连通图的定义*/Þ：如果G强连通，G中的顶点为v1，v2，….vn,设v1到v2路径为P1，v
87、2到v3的路径为P2，……，vn到v1的路为Pn，将P1，P2，…...Pn连起来，此路是一条长度为n基本回路。/*长度为n基本回路包含了n个不同的顶点*/2三、用狄克斯特洛算法求下图中u到c的最短通路。bacd762fe8144347235631u000g参考答案一、写出集合{Æ,{Æ}}的幂集。参考答案Æ，{Æ}，{{Æ}}，{Æ,{Æ}}。二、画出4阶无向完全图K4的所有含有3条边的生成子图。参考答案三、证明n阶有向完全图的边数为n2。参考答案设n阶有完全图的边数为m，则图中所有点的度数和为2m。而n阶无向完全图的每个
88、顶点都与其它顶点都有两条方向相反的边相连，并且有自回路，故图中每个点度数都为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)(2)邻接矩阵：V1V2V3V4V10100V20011V31101V41000一、设G是n阶无向简单图，若G中任意不同的两个顶点
89、的度数之和大于等于n–1，试证明G是连通图。参考答案反证法。假设G不连通。不妨设G有k个连通分支，n1，n2，……，nk是各分支的顶点数。显然有：n1+n2+nk=n①任取uÎG1,则deg(u)<=n1–1vÎG2,则deg(v)<=n2–1于是：deg(u)+deg(v)=n1–1+n
