99年國立台北市立教育大學資工所離散數學

Define the following graph terminologies:

1.

Planar graph

Define the following graph terminologies:

2.

Hamilton circuit

Define the following graph terminologies:

3.

Euler path

Define the following graph terminologies:

4.

Chromatic number

Define the following graph terminologies:

5.

Bipartite graph

Consider relations and their properties:

6.

What is a reflexive relation?

Consider relations and their properties:

7.

What is a transitive relation?

Consider relations and their properties:

8.

What is an antisymmetric relation?

Consider relations and their properties:

9.

Define a partial ordering

Consider relations and their properties:

10.

Define a lattice.

Briefly answer the following terms:

11.

Halting problem

Briefly answer the following terms:

12.

NP-complete

13.

How many solutions are there to the equation x₁ + x₂ + x₃ + x₄ + x₅ ≤ 29, where x_i, i = 1, 2, 3, 4, 5 is an nonnegative integer.

A string that contains only 0s, 1s, and 2s is called a ternary string.

14.

Find a recurrence relation for the number of ternary strings that contain two consecutive 0s.

A string that contains only 0s, 1s, and 2s is called a ternary string.

15.

What are the initial conditions?

Give a deterministic finite automata (DFA) accepting the following languages over the alphabet {0, 1}:

16.

The set of strings with three consecutive 0's.

Give a deterministic finite automata (DFA) accepting the following languages over the alphabet {0, 1}:

17.

The set of all stings beginning with a 1 which, interpreted as the binary representation of an integer, is congruent to zero modulo 5.

18.

A chess player is the champion for a period of 11 weeks. The chess player had won at least 1 game per day, but no more than 12 games per week. Use the pigeonhole principle to show that there is a period of consecutive days during which the chess player had exactly won 21 games.

19.

Let p = 13 and q = 7. Find a minimum positive integer d such that (((72)⁵)^d mod 91) = 72. You need to explain how you derive the answer.

20.

Find the shortest path from S to T of Graph (a) by Dijkstra's algorithm step by step.

21.

A finite state machine given in the state diagram shown in following figure (b). Determine a minimum finite state machine that is equivalent to it.