课程名称︰离散数学
课程性质︰电机系复选必修
课程教师︰陈和麟
开课学院：电机资讯学院
开课系所︰电机工程学系
考试日期（年月日）︰2018/06/29
考试时限（分钟）：110
试题 :
Please answer the following questions on the answer sheets provided. Be sure
to write your name and student ID on all answer sheets you use. You may bring
one A4-sized, hand-written, double-sided "cheat sheet". No other nooks, notes,
or calculators may be used during the exam.
If you want ti use any result or theorem that has been taught in class (
including homeworks), you may do so but you must state the result or theorem
clearly before using it.
Please read all problems first. No questions allowed after 13:50.
Problem 1
1. (13%) Solve T(n) = 4T(n-1) - 3T(n-1) - 10, T(0) = 2, T(1) = 9
2. (12%) Solve nT(n) = (2n-2)T(n-1) + log2[n/(n-1)^2], T(1) = 2
Problem 2
Let R1 and R2 be two relations defined on set A = {1,2,3,4,5}.
┌ ┐ ┌ ┐
1│1 0 0 0 0│ 1│1 1 0 0 0│
2│0 1 0 0 0│ 2│1 1 0 0 0│
M_R1 = 3│0 1 1 0 0│ M_R2 = 3│0 0 1 1 1│
4│0 1 0 1 0│ 4│0 0 1 1 1│
5│0 1 1 1 1│ 5│0 0 1 1 1│
└ ┘ └ ┘
1. Draw the Hasse diagram of R1.
2. Identify all maximal and minimal elements of R1.
3. Split A into equivalence classes of R2.
4. Compute R1。R2.
(No explaination needed for problem 2.)
Problem 3
1. (6%) Let R be an antisymmetric relation on A and R1 ⊆ R. Is R1 always
antisymmetric? Prove your answer.
2. (8%) Let R be an relation on A such that R^3 ⊆ R. Is R^5 ⊆ R always true?
Prove your answer.
Problem 4
given two undirected graphs G1 = (V1, E1) and G2 = (V2, E2) such that
‧V1 = {v1,v2,v3,v4,v5,v6,v7,v8,v9}
‧E1 = {{vi,vj} | i - j ≡ 1 or -1 or 2 or -2 (mod 9)}
‧The adjacency matrix of G2 is
┌ ┐
u1│0 0 0 1 1 1 0 0 0│
u2│0 0 0 1 1 1 0 0 0│
u3│0 0 0 1 1 1 0 0 0│
u4│1 1 1 0 0 0 1 1 1│
M_G2 = u5│1 1 1 0 0 0 1 1 1│
u6│1 1 1 0 0 0 1 1 1│
u7│0 0 0 1 1 1 0 0 0│
u8│0 0 0 1 1 1 0 0 0│
u9│0 0 0 1 1 1 0 0 0│
└ ┘
1. (3%) Is G1 isomorphic to G2? Prove your answer. You must either find the
mapping function for an isomorphism or prove that a specific invariant is not
preserved.
2. (3%) Does G2 have a Hamilton path? Prove your answer.
3. (9%) Suppose that we remove 4 edges from G1 and draw it on the plane
without edge crossings. How many regions does the drawing have? List all the
possible answers. Prove your answer.
Problem 5
Prove the following stements or find counter examples (and explain your
counter example breifly).
1. (18%) Let G be a simple undirected graph. κ(G) < n/2. If G is connected,
then G must contain a simple path of length at least 2κ(G). (Hint: consider
the longest simple path of G.)
2. (12%) Let G be a simple undirected simple graph. If G does not contain any
subdivision of K3,3 as a subgraph, then G must be planar.