Given the graph G = (V,E) and X is a vertex of G. Suppose there exists at least one Hamilton Cycle for the graph. The following is a backtracking algorithm for finding the first Hamilton cycle from the vertex X: declare an empty array H (which will contain Hamilton cycle) (1) Put the vertex X to H (2) Check if H is a Hamilton cycle then stop, else go to (3) (3) Consider the last vertex Y in H, if there is/are vertex(es) adjacent to Y, select the first adjacent vertex Z (by alphabet order) and put it to H. If there no adjacent vertex, remove Y from H and denote it as a bad selection (so you do not select it in the same way again). Go to (2). Suppose a G is given below (view picture). Which of the followings is the Hamilton cycle from the vertex A, created by above algorithm?

Đáp án đúng: "A, B, C, E, D, A". Chạy thuật toán từ A với luật luôn lấy đỉnh kề đầu tiên theo thứ tự chữ cái và chưa nằm trong H: từ A lấy B, từ B lấy C, từ C lấy D, từ D chỉ còn E nên lấy E. Tại E hai đỉnh kề là C và D đều đã trong H mà E lại không kề A, nên E bị gỡ và ghi là lựa chọn xấu; D cũng hết đỉnh để đi nên bị gỡ tiếp. Lùi về dãy A, B, C thì đỉnh kề kế tiếp của C sau D là E, đi E rồi từ E lấy D; lúc này H chứa cả năm đỉnh và D kề A nên chu trình đóng lại thành A, B, C, E, D, A. "A, B, C, D, E, A" sai vì E không kề A, hai cạnh duy nhất của E là E–C và E–D. "A, B, C, D, E, C, A" sai vì nó đi qua C hai lần, còn chu trình Hamilton phải thăm mỗi đỉnh đúng một lần. "A, C, D, E, B, A" sai vì bước đầu thuật toán buộc chọn B trước C theo thứ tự chữ cái, hơn nữa E không kề B. "A, D, E, C, B, A" tuy là một chu trình có thật trong đồ thị nhưng không phải thứ tự thuật toán sinh ra, vì từ A nó bỏ qua B để lấy D.