試題詳解

複選題
(56) Which of the followings is wrong?
(A) If a spanning tree has the maximum degree as 2, then it is a Hamiltonian path.
(B)If Problem III can be solved in polynomial time, then we can find a Hamiltonian path in polynomial time.
(C) Problem I can be solved with the Prim's algorithm..
(D) A graph can have more than one spanning tree.
(E) If P=NP, then Problem II can be solved in polynomial time.