《离散数学试卷B.docx》由会员分享，可在线阅读，更多相关《离散数学试卷B.docx（2页珍藏版）》请在三一文库上搜索。
1、精品文档B卷1. Show that (p q) p) ； q are tautologies. (10 scores)2. Suppose that f(x),g(x) and h(x) are functions such that f(x ) is；(g(x) and g(x) is 1(h(x).Show that f(x) is 1 (h(x).(10 scores)3. Let A110jand B =.Fi nd Bt At.(10 scores)4. Find a compatible total ordering for the poset (2,4,6,9,12,18,27
2、,36,48,60,72,|).(10 scores)5 . Let R be the relation on the set of ordered pairs of positive integers such that (a,b),(c,d)R ifand only if a+d = b + c. Show that R is an equivalence relation. (15 scores)6. Use adjace ncy matrix to find the nu mbers paths betwee n U 1 and U 5 in the graph in Figure1
3、of len gth 3, determ ine whether it is pla nar and if it is pla nar ,into how many regi ons does this graph split the pla ne? (10 scores)Figure 17. Suppose there are 7 finals to be scheduled so that no student has two exams at the same time. Suppose the courses are nu mbered 1 through 7. Suppose tha
4、t the follow ing pairs of courses have common stude nts : 1 and 2, 1 and 3, 1 and 4, 1 and 5, 2 and 3, 3 and 4 ,4 and 5.Please schedule the final exams for this. (10 scores)8 . Use Prim algorithm to find a minimum spannig tree in the following graphe,then use Kruskal s algorithm to find a minimum spannig tree in the same graph. (10 scores) 9. Suppose T is an ordered rooted tree.And the inorder listing of T is h,d,b,i,e,j,a,f,c,k,gThe preorder list ing of T is a,b,d,h,e,I,j,c,f,g,kPlease draw T and find the postorder listing of T. (15 scores)