99年國立台灣大學資工所離散數學

1.

以下敘述何者為正確? 請清楚標示答案, 不需說明。

(A)

R = {(1, 1), (2, 2), (3, 3), (4, 4), (5, 5)} is an equivalence relation on {1, 2, 3, 4, 5}.

(B)

There are 2²⁰ different reflexive binary relations on {1, 2, 3, 4, 5}.

(C)

Let R be a binary relation. Then is the reflexive transitive closure of R.

(D)

Let (K, ⋅, +) be a Boolean algebra. Then, a ⋅ (b + c) = (a ⋅ b) + (a ⋅ c) and a + (b ⋅ c) = (a + b) ⋅ (a + c) hold for all a, b, c ∈ K.

(E)

There exists a Boolean algebra (K, ⋅, +), where |K| = 6.

2.

以下敘述何者為正確? 請清楚標示答案, 不需說明。

(A)

Suppose there (R, +, ⋅) is a ring. If a ⋅ b = a ⋅ c, where a, b, c ∈ R and a is not the identity for +, then b = c.

(B)

Suppose that (R, +, ⋅) is a ring and S ⊂ R is not empty. If a + b, a ⋅ b ∈ S for all a, b ∈ S and −c ∈ S for all c ∈ S, where −c denotes the inverse of c under +, then (S, +, ⋅) is also a ring.

(C)

If (R, +, ⋅) is a field, then (R, +, ⋅) is also an integral domain.

(D)

Suppose that (G, ⋅) and (H, ∗) are two groups. A mapping f : G → H is a group isomorphism, if f(a ⋅ b) = f(a) ∗ f(b) for all a, b ∈ G

(E)

If (G, ⋅) is a group and a ∈ G, then ({ai | i ∈ Z}, ⋅) is also a group, where Z is the set of integers.

3.

以下敘述何者為正確? 請清楚標示答案, 不需說明。

(A)

There are 40 different ways to store 1, 2, 3, 4, 5 in A[1:5] (each number stored in a memory location) so that A[i] ≠ i for all 1 ≤ i ≤ 5.

(B)

f(x) = x/(1 − x)² is the ordinary generating function for 0, 1, 2, 3, 4, ….

(C)

There are 105 different integer solutions for x₁ + x₂ + x₃ + x₄ = 24, where 3 ≤ x_i ≤ 8 for i = 1, 2, 3, 4.

(D)

There are (5⁸ − 3⁸)/2 different ways to distribute 8 different objects O₁, O₂, …, O₈ to five different boxes B₁, B₂, …, B₅ provided an even number of objects are distributed to B₅.

(E)

Let a_n be the number of different quaternary (i.e., {0, 1, 2, 3}) sequences of length n that have an even number of 1's, where n ≥ 2. Then, a_n = 2a_n−1 + 4_n−1.

4.

以下敘述何者為正確? 請清楚標示答案, 不需說明。

(In the following, G = (V, E) is a simple, undirected, and weighted graph, where V = {v₁, v₂, …, v_n}. Also, let di be the degree of vi, where 1 ≤ i ≤ n.)

(A)

is even.

(B)

The connected components of G can be determined, as a consequence of executing a breadth-first search on G.

(C)

A spanning tree of G can result, as a consequence of executing a breadth-first search on G.

(D)

If all edge costs of G are distinct, then G has a unique minimum spanning tree.

(E)

A clique of G is a complete subgraph of G.

Let G = (V, E) be a simple undirected graph and δ be the minimum vertex degree of G, where |V| ≥ 3 and δ ≥ |V|/2 are assumed. The following is a proof of G having a Hamiltonian cycle.

Suppose to the contrary that G contains no Hamiltonian cycle. Further, we assume, without loss of generality, that G is a maximal nonhamiltonian simple graph. Let (u, v) ∉ E. So, G + (u, v), the resulting graph by augmenting G with (u, v), has a Hamiltonian cycle, denoted by (u =) v₁, v₂, …, v|V| (= v).
Set S = {v_i | (u, v_i+1) ∈ E and 1 ≤ i ≤ |V| − 1} and T = {v_i | (v_i, v) ∈ E and 1 ≤ i ≤ |V| − 1}. Then, |S ∪ T| < |V| and |S ∩ T| = 0, which implies d_u + d_v = |S| + |T| = |S ∪ T| + |S ∩ T| < |V| (d_u and d_v are the degrees of u and v, respectively), a contradiction to δ ≥ |V|/2.

5.

Why |S ∪ T| < |V|?

Let G = (V, E) be a simple undirected graph and δ be the minimum vertex degree of G, where |V| ≥ 3 and δ ≥ |V|/2 are assumed. The following is a proof of G having a Hamiltonian cycle.

Suppose to the contrary that G contains no Hamiltonian cycle. Further, we assume, without loss of generality, that G is a maximal nonhamiltonian simple graph. Let (u, v) ∉ E. So, G + (u, v), the resulting graph by augmenting G with (u, v), has a Hamiltonian cycle, denoted by (u =) v₁, v₂, …, v|V| (= v).
Set S = {v_i | (u, v_i+1) ∈ E and 1 ≤ i ≤ |V| − 1} and T = {v_i | (v_i, v) ∈ E and 1 ≤ i ≤ |V| − 1}. Then, |S ∪ T| < |V| and |S ∩ T| = 0, which implies d_u + d_v = |S| + |T| = |S ∪ T| + |S ∩ T| < |V| (d_u and d_v are the degrees of u and v, respectively), a contradiction to δ ≥ |V|/2.

6.

Why |S ∩ T| = 0?