109年 - 109 國立中山大學_碩士班招生考試_電機系(丙組)：離散數學#106106

試卷資訊

選擇題 (0)

申論題 (10)

1.1 True(O) or False(X): Assume that A and B are problems. If A is an NP one and B is in P, A N B is not NP-complete.

1.2 True(O) or False(X): If A is in NP-complete and A can be solved in polynomial time less than B, B belongs to NP-complete.

1.3 Truc(O) or False(X): Solutions to the class of NP problems can be verified in polynomial time.

1.4 True(O) or False(X): A class of NP problems without known polynomial algorithms that can be reduced to one another is called NP-complete.

2. Decide the complexity of the following computation. Please justify your answer.
Otherwise, you get O points.
If N and M are positive integers, then the complexity = O(L). What is L in
terms of N and M?

3.1 K3 (i.e., a complete graph with 3 vertices). (5 points)

3.2 K2,2 (i.e., a complete bipartite graph with 4 vertices). (15 points)

3.3 Find the total number of spanning trees of the graph. (15 points)

4. Use Dijkstra's algorithm to find the shortest path between V1 and V7. Please justify your answer. Otherwise, you get 0 points.

5. There are 12 students, and you are a coach. You want to divide the students into three specific groups, i.e.,G1, G2, and G3, so that each group contains four students. Please decide how many ways you can divide them. Please justify your answer.