作者boggart0803 (幻形怪)
看板NTU-Exam
标题[试题] 96下 颜嗣钧 离散数学 期末考
时间Tue Jun 17 11:51:36 2008
课程名称︰离散数学
课程性质︰必修
课程教师︰颜嗣钧
开课学院:电资学院
开课系所︰电机系
考试日期(年月日)︰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)