99年國立雲林科技大學資工所離散數學

For the directed graph specified below
G = (N, A), N(G) = {a, b, c, d}, A(G) = {<a, b>, <a, c>, <b, d>, <c, d>, <b, a>, <d, c>}

1.

Complete the directed graph.

For the directed graph specified below
G = (N, A), N(G) = {a, b, c, d}, A(G) = {<a, b>, <a, c>, <b, d>, <c, d>, <b, a>, <d, c>}

2.

Find the adjacency matrix of the graph

For the directed graph specified below
G = (N, A), N(G) = {a, b, c, d}, A(G) = {<a, b>, <a, c>, <b, d>, <c, d>, <b, a>, <d, c>}

3.

Find the adjacency list of the graph.

For the directed graph specified below
G = (N, A), N(G) = {a, b, c, d}, A(G) = {<a, b>, <a, c>, <b, d>, <c, d>, <b, a>, <d, c>}

4.

Depict the advantages and disadvantages of using the adjacency matrix and the adjacency list, respectively.

For the directed graph specified below
G = (N, A), N(G) = {a, b, c, d}, A(G) = {<a, b>, <a, c>, <b, d>, <c, d>, <b, a>, <d, c>}

5.

Please determine the coefficient of x¹⁵ in g(x) = (x² + x³ + x⁴ + ...)⁴.

Given a connected simple graph, G, consists of n vertices

6.

What is the minimum number of edges of G.

Given a connected simple graph, G, consists of n vertices

7.

What is the number of edges of the minimum spanning tree T of G.

Given a connected simple graph, G, consists of n vertices

8.

Two algorithms of Kruskal and Prim can be used to determine the minimum spanning tree. Please detail the differences between the Kruskal's and Prim's algorithms.

9.

Determine a_n, where a₁ = 1,

10.

an alphabet consists of the symbols 0, 1, and 2, then 01, 11, 21, 12, and 20 are five of the nine strings of length 2. Let n be any positive integer and x = x₁x₂...x_n be one of the strings of length n based on the above alphabet. We define the weight of x, denoted wt(x), by wt(x) = x₁ + x₂ + ... + x_n. For example, wt(12) = 3 and wt(22) = 4. Based on the alphabet given above, if n = 10, how many of the strings have even weight?

11.

Consider the following program segment, where i, j, and k are integer variables.
           for i := 1 to 20 do
               for j := 1 to i do
                   for k := 1 to j do
                          print(i ∗ j + k)
How many times is the print statement executed in this program segment?

12.

Please prove the Euclid theorem: There are infinitely many primes.

13.

Let m ∈ Z⁺ with m odd. Prove that there exists a positive integer n such that m divides 2ⁿ + 1.

14.

Consider a Turing machine that has the following two instructions:
          (1, 1, 0, 2, R),
          (2, 1, 1, 1, R).
Determine its output when it is run on the following tape. (Remember that a Turing machine starts in state 1, reading the leftmost nonblank cell.)