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, F, A". Đồ thị có các cạnh A–B, A–C, A–D, A–F, B–C, B–D, B–E, C–D, C–E, C–F, D–E, D–F, và không có A–E, B–F, E–F. Chạy quay lui từ A, mỗi bước lấy láng giềng đầu theo chữ cái: A chọn B, B chọn C, C chọn D, D chọn E; tới E thì B, C, D đều đã trong H mà H mới có 5 đỉnh, nên E bị loại và ghi là lựa chọn tồi; D chuyển sang F, nhưng F chỉ kề A, C, D nên không mở thêm được và H vẫn thiếu E, F cũng bị loại; D hết lựa chọn nên bị loại khỏi H; C chuyển sang E, E chọn D, D chọn F, lần này H đã đủ sáu đỉnh và F kề A nên đóng chu trình về A. Phương án "A, F, D, E, C, B, A" và phương án "A, F, C, E, D, B, A" đều hợp lệ về cạnh nhưng khởi đầu bằng F, trong khi từ A thuật toán luôn thử B trước. Phương án "A, F, D, B, E, C, A" cũng mắc lỗi khởi đầu ấy. Phương án "A, B, D, E, C, F, A" chọn D ngay sau B, trong khi láng giềng chưa dùng của B theo chữ cái là C đứng trước D.