試題詳解

21. Which of the following statements about Hamilton Path/Circuit is True?
(A) A Hamiltonian path is a path in an undirected or directed graph that visits each edge exactly once.
(B) Determining whether Hamiltonian paths and cycles exist in graphs is polynomial.
(C) A simple graph with n vertices (n ＞= 3) is Hamiltonian if every vertex has degree n / 2 or greater.
(D) A graph with n vertices (n ＞= 3) is Hamiltonian if, for every pair of non-adjacent vertices, the sum of their degrees is n/2 or greater.