96年國立中央大學企管所離散數學

Permutations and Combinations

1.

At high school, the gym teacher must make up four volleyball terms of nine boys each from the 36 freshman boys in her class. In how many ways can she select these four terms? Call the A, B, C and D.

Permutations and Combinations

2.

Suppose that Ellen draws five cards from a standard deck of 52 cards. In how many ways can her selection that contains at least one diamond?

Set Theory
Let A, B, C are universal sets. Prove or disprove (with an example) each of the following:

3.

A − C = B − C ⇒ A = B

Set Theory
Let A, B, C are universal sets. Prove or disprove (with an example) each of the following:

4.

[(A ∩ C = B ∩ C) AND (A − C = B − C)] ⇒ A = B

Set Theory
Let A, B, C are universal sets. Prove or disprove (with an example) each of the following:

5.

[(A ∪ C = B ∪ C) AND (A − C = B − C)] ⇒ A = B

6.

Using the principle of mathematical induction to prove that for each n ∈ Z⁺,

Mathematical Induction

7.

Let n ∈ Z⁺ where n ≥ 2, and let A₁, A₂, …, A_n are universal sets for each 1 ≤ i ≤ n. Then

8.

Recurrence Relations
Solve the relation a_n − 3a_n−1 = n, n ≥ 1, a₀ = 1.

Graph Theory with Applications

9.

Let G = (V, E) be the undirected graph. How many paths are there in G from a to h? How many of these paths have length 5?

Graph Theory with Applications

10.

Let G = (V, E) be an undirected graph representing a selection of a department store. The vertices indicate where cashiers are located; the edges denote unblocked aisles between cashiers. The department store wants to set up a security system where guards are placed at certain cashier locations so that each cashier either has a guard at his or her location or is only one aisle away from a cashier who has a guard. What is the smallest number of guards needed?

 

11.

Trees
Please give an example to explain the following lemma:
Let G = (V, E) be a loop-free connected undirected graph with T = (V, W) a depth-first spanning tree of G. If r is the root of T, then r is an articulation point of G if and only if r has at least two children in T.

The Algorithms of Kruskal and Prim

12.

State the basic idea of Kruskal's algorithm.

The Algorithms of Kruskal and Prim

13.

Apply Prim's algorithm to determine minimal spanning tree for the following graph.

14.

The Max-Flow Min-Cut Theorem
Prove or give an example to explain the following statement:
For a transport network N = (V, E), the maximal flow value that can be attained in N is equal to the minimal capacity over all cuts in the network.

15.