課程名稱︰離散數學 課程性質︰必修 課程教師︰顏嗣鈞 開課學院：電資學院 開課系所︰電機系 考試日期（年月日）︰2008/06/16 考試時限（分鐘）：120分鐘 是否需發放獎勵金：是 （如未明確表示，則不予發放） 試題： 1. (10 pts) Solve the following recurrence relation h_n precisely. Show your derivation in detail. h_n=2h_(n-1)+3h_(n-2)+4n; h_0=1;h_1=4 2. (8 pts) A graph is simple if it does not contain self loops or multiple edges. Given a simple graph G=(V,E) with V={v_1,v_2,…,v_m}, the degree sequence of G is (n_1,n_2,…,n_m) where n_i is the degree of vertex v_i, 1≦i≦m. (a) Is it possible to draw a simple graph with degree sequence (4,4,4,4,3)? Justify your answer. (b) Does a simple graph G with degree sequence (4,4,4,3,3) always have a Hamilton cycle? Justify your answer. 3. (8 pts) Given a simple graph G=(V,E), the complement of G, denoted by G', is (V,E'), where E'= {(x,y)| x≠ y, (x,y) does not belong to E}, i.e., (x,y) is an edge of G' iff (x,y) is not an edge of G. Prove formally that for an n-node graph G (i.e., |V|=n), if both G and G' are planar, then n≦10. (Hint: Use Euler formula.) 4. (7 pts) Prove that every simple planar graph has a vertex of degree≦5. (Hint: Use Euler formula.) 5. (9 pts) Given a graph G, χ(G,λ) denotes the chromatic polynomial (with variable λ) which is the number of different ways that G can be colored with λ colors. For example, the chromatic polynomial of a line o-o-o-o is λ×(λ -1)^3 For a graph H=(V,E) with E≠ψ, suppose we know χ(G,λ)=λ^5-5λ^4+10λ^3 -□λ^2+3λ. (1) What is the value of the missing coefficient "□"? Why? (2) How many nodes does H have? Why? (3) Prove that H is a bipartite graph. 6. (12 pts) For which values of m and n does the complete bipartite graph K_m,n have a(an) (1) Euler circuit? (2) Euler path? (3) Hamilton circuit? (4) Planar embedding? Make sure that your answers are as general as possible. 7. (12 pts) Let R= {(a,c),(b,d),(c,a),(d,b),(e,d)} be a relation defined on {a,b,c,d,e}. (a) Give (draw) the graph representation of relation R. (b) Compute R^2. (c) Find the transitive closure of R. 8. (24 pts) Complete the following table. Fill in O (resp., X) if a relation type is close (resp., not close) under an operation. (No penalty for wrong answer.) A and B are binary relations over set X. A-B denotes {x| x belongs to A, x does not belong to B} (i.e., the difference of A and B); A'= (X×X)-A (i.e., the complement of A). For example, the entry for ("Symmetric", "A∪B") asks whether given two symmetric relations A and B, A∪B is always symmetric? | A∩B | A∪B | A-B | A' | Reflexive | | | | | Symmetric | | | | | Transitive | | | | | Antisymmetric | | | | | Asymmetric | | | | | Partial order | | | | | 9. (10 pts) Consider the following relation ≦ on the set N×N (where N= {0,1, 2,…} is the set of natural numbers): (a,b)≦(c,d) iff a≦c and b≦d. Answer the following yes-no questions: (No penalty for wrong answer). The relation "≦" is (1) reflexive? (2) symmetric? (3) antisymmetric? (4) asymmetric? (5) transitive? (6) well-ordered? (7) a partial-order relation? (8) an equivalence relation? (N×N,≦) has a (9) least element? (10) greatest element? --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 220.133.169.66 ※ 編輯: boggart0803 來自: 220.133.169.66 (06/18 10:45)