19. Problem I: Given a graph G = (V, E), is there a minimum-degree spanning tree T of maximum degree two, where the minimum-degree means that the maximum degree is minimized?
Problem II: Given an undirected graph and a positive integer K, is there a path of length at most K, where each edge has weight 1 and each vertex is visited exactly once?
Problem III: Given an undirected graph and a positive integer K, is there a path of length at least K, where each edge has weight 1 and each vertex is visited at most once?
【題組】(55) Which of the following statements is wrong?
(A) A problem is NP-complete, if it belongs to the class NP and all the other members in NP can be reduced to it in polynomial time.
(B) Problem I belongs to NP.
(C) Problem III belongs to NP.
(D) Problem III is NP-complete.
(E) If we change the graph in Problem IlI to directed graph, then it belongs to P.