Đường đi
Số nút đã duyệt
Chu trình Hamilton
Đường đi Hamilton

Chế độ

    Mục tiêu

    Tìm hiểu thêm về đường đi và chu trình Hamilton

    Trình khám phá đường đi Hamilton

    Năm 1857 William Rowan Hamilton nghĩ ra một câu đố: đi dọc các cạnh của một khối mười hai mặt sao cho qua mỗi góc trong 20 góc đúng một lần rồi kết thúc đúng chỗ xuất phát. Lộ trình như vậy ngày nay gọi là chu trình Hamilton. Kiểm tra thì dễ, còn tìm ra thì thường rất khó. Hãy tự vẽ một lộ trình trên khối mười hai mặt của Hamilton, trên bàn cờ, hoặc trên đồ thị bạn vẽ; hoặc xem phép tìm quay lui truy lùng nó, đếm những ngõ cụt nó rơi vào, và thấy vài phép kiểm đơn giản rút ngắn cuộc tìm đến mức nào. Chọn một đồ thị và một mục tiêu: chu trình quay về điểm xuất phát, hoặc một đường đi. Vẽ theo: bấm vào một đỉnh để bắt đầu, rồi mỗi lần bấm một đỉnh kề; các vòng nét đứt cho thấy bạn có thể đi tiếp đến đâu. Bấm vào đỉnh cuối, bấm Lùi hoặc Hoàn tác để lùi một bước, còn Gợi ý chỉ ra một bước tiếp theo vẫn còn đi hết được. Tìm kiếm: Chạy hoặc Từng bước cho chạy phép tìm quay lui, nó thêm đỉnh cho đến khi tắc rồi quay ngược lại; nét đứt đỏ cho thấy chỗ nó quay lui, còn các cột đếm số nút theo chiều dài đường đi. Trước khi bắt đầu, bấm vào một đỉnh để chọn nơi xuất phát. Các ô đánh dấu bật tắt việc cắt tỉa, So sánh chạy cùng một phép tìm có và không có cắt tỉa, còn Đếm tất cả đếm mọi chu trình hay đường đi của một đồ thị nhỏ. Sửa: bấm để thêm một đỉnh, bấm hai đỉnh để nối hoặc tách chúng, kéo để di chuyển một đỉnh, và Xóa bỏ đỉnh đang chọn.

    Cách nó hoạt động

    1. Chọn một đồ thị, chẳng hạn khối mười hai mặt của Hamilton, đồ thị Petersen hay một hành trình quân mã, hoặc tự vẽ đồ thị trong chế độ Sửa, rồi chọn mục tiêu là chu trình hay đường đi.
    2. Ở chế độ Vẽ theo, bấm vào một đỉnh để bắt đầu rồi bấm lần lượt từng đỉnh kề. Lùi và Hoàn tác lùi một bước, còn Gợi ý chỉ ra một bước tiếp theo vẫn còn đi hết được.
    3. Ở chế độ Tìm kiếm, bấm Chạy hoặc Từng bước để xem phép quay lui dò tìm lộ trình, bật tắt việc cắt tỉa, rồi bấm So sánh để xem mỗi phiên bản cần bao nhiêu nút.

    Hamilton so với Euler

    Đường đi Euler dùng mỗi cạnh một lần; đường đi Hamilton qua mỗi đỉnh một lần. Nghe thì giống nhau nhưng tính chất rất khác. Một đồ thị liên thông có đường đi Euler hay không được quyết định bằng cách đếm các đỉnh bậc lẻ, như Euler đã chỉ ra năm 1736: có khi không có đỉnh nào như vậy hoặc có đúng hai. Với đường đi Hamilton thì chưa có quy tắc nào như thế. Quyết định một đồ thị có chu trình Hamilton hay không là bài toán NP-đầy đủ, một trong 21 bài toán trong danh sách năm 1972 của Richard Karp, nên một phương pháp nhanh cho nó sẽ cho phương pháp nhanh với hàng nghìn bài toán khó khác. Cái đang có là những điều kiện giải quyết được một số đồ thị. Định lý Dirac năm 1952 bảo đảm có chu trình Hamilton khi mọi đỉnh đều có bậc ít nhất n/2, còn định lý Ore năm 1960 thì khi hai đỉnh không kề nhau luôn có tổng bậc ít nhất n; đỉnh bậc 1, đỉnh cắt hay hai lớp màu khác kích thước đều loại trừ nó.

    Phép tìm hoạt động thế nào

    Phép quay lui dựng đường đi từng đỉnh một và khi tắc thì rút lại bước cuối rồi thử đỉnh kề tiếp theo. Nếu có chu trình Hamilton thì nó luôn tìm ra, nhưng số đường đi dang dở có thể tăng theo cấp số nhân. Trên lưới 5 × 5, vốn không có chu trình Hamilton, phép quay lui thường phải duyệt 153.745 nút mới chắc chắn. Hai phép kiểm chặn sớm những đường vô vọng: một đỉnh chưa thăm mà còn chưa tới hai đỉnh kề trống thì không thể xếp vào chu trình nữa, và khi các đỉnh chưa thăm tách thành những phần rời nhau thì không một đường đi đơn nào phủ hết được. Dùng cả hai, cũng chứng minh ấy chỉ tốn 1.761 nút. Quy tắc Warnsdorff năm 1823, thử trước đỉnh kề có ít nước đi tiếp theo nhất, tìm ra hành trình quân mã 8 × 8 xuất phát từ một góc trong 64 nước mà không gặp một ngõ cụt nào.

    Câu hỏi thường gặp

    Đường đi Hamilton và chu trình Hamilton khác nhau thế nào?

    Đường đi Hamilton qua mỗi đỉnh của đồ thị đúng một lần. Chu trình Hamilton cũng vậy rồi đi thêm một cạnh nữa để quay về chỗ xuất phát, nên nó có thể bắt đầu từ bất kỳ đỉnh nào của mình. Mọi đồ thị có chu trình Hamilton đều có đường đi Hamilton (chỉ cần bỏ một cạnh của chu trình), nhưng chiều ngược lại thì không: đồ thị Petersen có đường đi Hamilton mà không có chu trình Hamilton.

    Khối mười hai mặt có chu trình Hamilton không?

    Có, 30 chu trình, nếu tính mỗi chu trình một lần bất kể điểm xuất phát và chiều đi. Năm 1857 Hamilton biến câu hỏi đó thành trò chơi icosian, một bàn chơi với 20 góc của khối mười hai mặt được dàn phẳng và ghi bằng các phụ âm, rồi bán bản quyền 25 bảng cho hãng đồ chơi London John Jaques and Son. Đếm tất cả trong ứng dụng tìm ra 30 chu trình ấy trong khoảng 1.400 nút.

    Vì sao lưới 5 × 5 không có chu trình Hamilton?

    Hãy tô 25 điểm như bàn cờ: 13 điểm mang một màu, 12 điểm mang màu kia, và mỗi bước lại sang màu khác. Chu trình luân phiên màu suốt vòng nên cần số điểm hai màu bằng nhau, mà 13 và 12 thì không. Lập luận ấy đúng cho mọi lưới có số điểm lẻ, cho quân mã trên bàn 5 × 5 hay 7 × 7 (quân mã luôn đổi màu ô), và cho đồ thị Herschel, hai lớp của nó có 6 và 5 đỉnh. Đường đi Hamilton thì vẫn có thể: nó bắt đầu và kết thúc ở màu đông hơn.

    Quy tắc Warnsdorff tìm hành trình quân mã bằng cách nào?

    Năm 1823 H. C. von Warnsdorff đề nghị luôn đưa quân mã tới ô mà từ đó nó có ít nước đi tiếp theo nhất. Nhờ vậy, những ô gần mép và gần góc, vốn dễ bị cắt đứt, được thăm sớm khi quân mã còn vào được. Quy tắc này là kinh nghiệm chứ không phải bảo đảm, và khi hòa thì phải phân xử bằng cách nào đó, nhưng trên bàn 8 × 8 nó thường hoàn tất hành trình mà không phải quay lui. Kết hợp với phép quay lui như trong ứng dụng này, nó tìm được hành trình mở từ 5 × 5 trở lên và hành trình khép kín trên bàn 6 × 6 và 8 × 8.

    Đồ thị đầy đủ có bao nhiêu chu trình Hamilton?

    (n − 1)!/2 với n ≥ 3. Cố định đỉnh xuất phát; n − 1 đỉnh còn lại có thể xếp theo thứ tự bất kỳ, và mỗi chu trình được đếm hai lần, mỗi chiều một lần. K₆ có 5!/2 = 60 và K₁₀ có 181.440. Đó chính là những vòng đi mà người chào hàng phải chọn, và vì vậy việc thử hết mọi khả năng rất nhanh trở thành bất khả thi.

    Sẵn sàng thử chưa?

    Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.

    Tới trình chỉnh sửa