課程名稱︰離散數學
課程性質︰必修
課程教師︰顏嗣鈞
開課學院：電資學院
開課系所︰電機系
考試日期（年月日）︰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)