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 B, created by above algorithm?

Đáp án đúng: "B, A, C, F, D, E, B". Đồ 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; thuật toán luôn chọn đỉnh kề chưa dùng đứng đầu theo chữ cái và quay lui khi bế tắc. Từ B chọn A, từ A chọn C, từ C chọn D. Tại D chọn E, nhưng E chỉ kề B, C, D đều đã nằm trong H mà H chưa đủ sáu đỉnh, nên E bị loại và quay lui; thử F cũng bế tắc vì F chỉ kề A, C, D. Quay lui thêm một bước, tại C thử E thì được B, A, C, E, D, F nhưng F không kề B nên không đóng được chu trình. Quay lui nữa, tại C chọn F, rồi F chọn D, rồi D chọn E; lúc này H đủ sáu đỉnh và E kề B nên chu trình đóng thành B, A, C, F, D, E, B. "B, A, F, D, E, C, B" và "B, A, F, C, D, E, B" đều chọn F tại A, trong khi C đứng trước F theo chữ cái và nhánh qua C chưa cạn. "B, C, E, D, F, A, B" bỏ A ngay bước đầu dù A là đỉnh kề đầu tiên của B. "B, D, A, F, C, E, B" bỏ qua cả A và C tại B.