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

一、 写出集合a,b,c的幂集。参考答案：P(A) = ,c,b,b,c,a,a,c,a,b,a,b,c二、 设A=a，b，c，B=0，1，求AP(B) （P(B)是B的幂集）参考答案AP(B)=, , 三、 70名学生参加体育比赛，短跑得奖者36人，弹跳得奖者29人，投掷得奖者36人；三项都得奖者6人；仅得两项奖的有24人。求一项都没有得奖的人数。参考答案：设R=短跑得奖者；J=弹跳得奖者；T=投掷得奖者；一项奖都没得的人数 = |(RJT)| = |U|-| RJT |根据容斥原理，|RJT| = |R|+|J|+|T|-|RJ |-|R T|-| JT|+|RJT|而仅得两项奖的人数 = (|RJ |-|RJT|)+(|R T|-|RJT|)+(| JT|-|RJT|) = (|RJ |+|R T|+| JT|)-3|RJT|故|RJ |+|R T|+| JT|=仅得两项奖的人数+3|RJT|因此，|RJT| = |R|+|J|+|T|-(|RJ |+|R T|+| JT|)+ |RJT| = |R|+|J|+|T|-仅得两项奖的人数-2|RJT| = 36+29+36-24-12=65一项奖都没得的人数 = |(RJT)| = |U|-| RJT |=70-65=5四、 设 A=1,2,3,4,5,8, 求R = | x, yA xy(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）关系图 (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为该等边三角形的重心。边长为a的三角形的面积是：， 若7个点都在一条直线上，则任意三个点连成的图形面积都为0。命题得证。若7个点不全在一条直线上，故根据鸽洞原理，至少有三个点落在gab、gac或gbc这三个三角形内部。不失一般性，设x、y和z三个点落在三角形gab中，则三角形xyz的面积gab的面积=。 故命题得证。七、 证明：一个简单有向图G是强连通的 G中有一条包含所有顶点的基本回路。参考答案 ： 中有一条包含所有顶点的基本回路，显然强连通。/*连通图的定义*/ ：如果 G强连通，G中的顶点为v1，v2，.vn, 设v1到v2路径为P1，v2到v3的路径为P2 ， vn到v1 的路为Pn ，将P1， P2，. Pn连起来，此路是一条长度为n基本回路。/*长度为n基本回路包含了n个不同的顶点*/2八、 用狄克斯特洛算法求下图中u到c的最短通路。bacd762fe8144347235631u000g参考答案九、 写出集合,的幂集。参考答案，,。十、 画出4阶无向完全图K4的所有含有3条边的生成子图。参考答案十一、 证明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) (2) 邻接矩阵：V1V2V3V4V10100V20011V31101V41000十三、 设G是n阶无向简单图，若G中任意不同的两个顶点的度数之和大于等于n1，试证明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)=n11+n21=n2 与题设“任意不同的两个顶点的度数之和大于等于n1”矛盾。 G是连通图 十四、 证明：模K关系是任何整数集A上的等价关系。参考答案若A= 则结论成立。若A不为，则 i) 自反的：aA a-a=0k aa(mod k)ii) 对称的：若ab(mod k) 则a-b=mk, b-a=(-m)k ba(mod k)iii) 传递的：若ab(mod k) bc(mod k) 则a-b=m1k b-c=m2ka-c=(a-b)+(b-c)= m1k + m2k =(m1m2)ka c(mod k)十五、 求带权为1, 1, 2, 3, 4, 5的最优树。参考答案W(T) = 2 + 4 + 7 + 16 + 9 = 38十六、 用狄克斯特洛算法求下图中a到z的最短通路。十七、 已知权值 W= 7，8，9，12，16 (1) 画出一棵最优树，并求出该最优树的权值。(2) 请依据最优树，为每个节点设计一种最优前缀码的编码方案。参考答案（1）最优树的权值为： W=(7+8)3(9+12+16)2=45+74=119（2）9：00 ，12：01，7：100，8：101，16：11十八、 设A=2,3,4,6,12，若关系R为定义在A上的整除关系，请回答下列问题。 (1)请画出A的哈斯图 (2)请根据关系R给出A的极大、极小、最大和最小元。 (3)请给出集合4,6,12的极小元及下确界。参考