104年 - 104 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105845

(a) Partial ordering relation

(b) Planar graph

(c) Left coset

(a) If R induces the partition A = {a} U {b, c} U{d, e}U{ f,g, h}, what is R?

(b) If R induces the partition A = A₁ UA₂U... .. U where n is a positive integer, then |R| = ?

(c) How many relations on A are equivalence relations that satisfy b ∈ [h]?

3. Construct a state diagram for a finite state machine with the input alphabet I= fa, by and the output alphabet O= (0, 13 that recognizes all strings in {b, a} *{bb} U {a, b}*{aa}. Note that the state diagram should contain 3 states only or get no credits.

(a) Iff(x) is the generating function of a sequence, what is the sequence?

(b) If g(x) is the exponential generating function of a sequence, what is the sequence?

(c) Use f(x) and g(x) to express the generating function for the number of integer solution, = 100 with c₁ ≥ 0 and c₂ ≥ 1, such that the answer is the coefficient of

(a)

(b)

(c)

(d) ,n≥ 2, a₀= 1, a₁ = 1. Note that the solutions should contain real numbers only or get no credits.

6. Let G =(V, E) be a loop-free graph with |V| =n≥ 2. For all x,y ∈ Vand x≠y, deg(x)+deg(v) ≥ n-1. Prove that G is connected.

7. Prove that an integral domain (T, +, ') is a field if it is finite.

104年 - 104 國立中山大學_碩士班招生考試_資工系(甲組)：離散數學#105845

試卷資訊

選擇題 (0)

申論題 (16)