Giải thích đường đi và chu trình Hamilton
Vẽ năm chấm thành vòng, nối mỗi chấm với hai chấm bên cạnh, và bạn có thể đi vòng qua mỗi chấm một lần rồi về nhà: đó là chu trình Hamilton. Thêm vài cạnh hoặc bớt vài cạnh thì câu hỏi trở nên khó một cách đáng ngạc nhiên. Một đồ thị có chu trình như vậy hay không là một trong những bài toán nổi tiếng nhất mà chưa máy tính nào trả lời nhanh được cho mọi đồ thị.
Mỗi đỉnh một lần
Đồ thị là một tập hợp các điểm gọi là đỉnh, nối với nhau bằng các đường gọi là cạnh. Đường đi Hamilton men theo các cạnh và qua mỗi đỉnh đúng một lần; chu trình Hamilton còn quay về chỗ xuất phát, nên số cạnh bằng số đỉnh. Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton. Kiểm tra một lộ trình cho sẵn thì dễ: đếm các đỉnh và xem từng bước. Tìm ra một lộ trình, hay chứng minh không có lộ trình nào, mới là phần khó, vì số thứ tự có thể thăm các đỉnh tăng như n!, với 20 đỉnh đã là 2,4 × 10¹⁸.
Trò chơi icosian của Hamilton
William Rowan Hamilton, nhà toán học Ireland đã khám phá ra quaternion, nghĩ ra trò chơi icosian năm 1857. Bàn chơi vẽ một khối mười hai mặt dàn phẳng trên mặt phẳng, với 20 góc ghi bằng các phụ âm, và nhiệm vụ chính là cắm các chốt đánh số từ 1 đến 20 lên các góc sao cho những số liên tiếp, cũng như 20 và 1, được nối bằng cạnh. Hamilton bán bản quyền 25 bảng cho hãng đồ chơi London John Jaques and Son; trò chơi ra mắt năm 1859 và bán không chạy. Câu đố có 30 lời giải, 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. Bản thân câu hỏi không mới: trong một bài gửi Hội Hoàng gia năm 1855, Thomas Kirkman đã hỏi những khối đa diện nào có chu trình qua tất cả các góc, và đã chỉ ra một khối không có.
Hành trình quân mã
Hành trình quân mã di chuyển quân mã trong cờ vua sao cho nó đặt chân lên mỗi ô đúng một lần: đó là đường đi Hamilton trong đồ thị có đỉnh là các ô và cạnh là các nước mã. Hành trình khép kín kết thúc cách điểm xuất phát đúng một nước mã, tức là một chu trình Hamilton. Người chơi cờ đã đặt ra những câu đố như vậy hơn một nghìn năm trước, và Euler nghiên cứu chúng trong một bài viết năm 1759. Năm 1823 H. C. von Warnsdorff đề nghị luôn đi tới ô có ít nước đi tiếp theo nhất; quy tắc đơn giản này thường hoàn tất hành trình trên bàn 8 × 8 mà không phải quay lui. Quân mã luôn đổi màu ô, nên hành trình khép kín cần số ô sáng bằng số ô tối, điều đó loại trừ những bàn có số ô lẻ. Năm 1991 Allen Schwenk chỉ ra chính xác những bàn hình chữ nhật nào có hành trình khép kín; trong số bàn vuông, mọi bàn có cạnh chẵn từ 6 trở lên đều có. Bàn cờ thông thường có 13.267.364.410.532 hành trình khép kín, do Brendan McKay đếm năm 1997.
Những đồ thị không có chu trình Hamilton
Cách chứng minh nhanh nhất rằng không có chu trình là lập luận đếm. Nếu có thể tô các đỉnh bằng hai màu sao cho mọi cạnh đều nối hai màu khác nhau thì chu trình luân phiên màu và cần số đỉnh mỗi màu bằng nhau; lưới 5 × 5 có 13 đỉnh màu này và 12 đỉnh màu kia, nên nó không có chu trình Hamilton. Đỉnh cắt, mà bỏ đi thì đồ thị tách ra, sẽ phải đi qua hai lần, còn đỉnh bậc 1 thì không thể đi xuyên qua. Một số đồ thị thoát khỏi mọi lập luận như thế. Đồ thị Petersen, do Julius Petersen công bố năm 1898, có 10 đỉnh bậc 3 và không có chu trình Hamilton, vậy mà bỏ đi bất kỳ đỉnh nào cũng còn lại một đồ thị có chu trình; đó là đồ thị hypohamilton nhỏ nhất. Đồ thị Herschel, đặt theo tên Alexander Stewart Herschel, người viết về trò chơi icosian năm 1862, có 11 đỉnh và 18 cạnh và là đồ thị của một khối đa diện với chín mặt tứ giác. Không khối đa diện nào ít góc hơn mà lại thiếu chu trình Hamilton. Năm 1884 Peter Guthrie Tait phỏng đoán rằng mọi khối đa diện có ba cạnh ở mỗi góc đều có chu trình Hamilton; năm 1946 W. T. Tutte tìm ra phản ví dụ với 46 đỉnh.
Những điều kiện bảo đảm có chu trình
Nếu một đồ thị có nhiều cạnh thì chắc chắn có chu trình Hamilton. Năm 1952 Gabriel Dirac chứng minh rằng đồ thị có n ≥ 3 đỉnh mà mọi đỉnh đều có bậc ít nhất n/2 thì có chu trình Hamilton, và năm 1960 Øystein Ore làm yếu điều kiện: chỉ cần hai đỉnh không kề nhau luôn có tổng bậc ít nhất n. Cả hai điều kiện chỉ đúng theo một chiều. Một vòng đơn gồm 100 đỉnh có bậc 2 ở khắp nơi, thấp hơn 50 rất nhiều, vậy mà bản thân nó là một chu trình Hamilton. Bức tranh chung là thế: có những điều kiện đủ và có những lý do thất bại, còn ở giữa trải ra một vùng rộng lớn gồm các đồ thị mà chỉ phép tìm mới quyết định được.
Vì sao chưa có phép thử nhanh nào được biết
Quyết định một đồ thị có chu trình Hamilton hay không là bài toán NP-đầy đủ; nó là một trong 21 bài toán trong danh sách năm 1972 của Richard Karp. Một phương pháp giải nhanh nó cho mọi đồ thị cũng sẽ giải nhanh hàng nghìn bài toán khác và sẽ giải quyết câu hỏi P với NP. Sự tương phản với đường đi Euler, vốn dùng mỗi cạnh một lần, thật rõ rệt: năm 1736 Euler chỉ ra rằng đếm các đỉnh bậc lẻ là trả lời được ngay câu hỏi ấy. Những phương pháp chính xác tốt nhất cho chu trình Hamilton vẫn tốn thời gian hàm mũ. Quy hoạch động trên mọi tập con của các đỉnh, do Richard Bellman và do Michael Held cùng Richard Karp tìm ra năm 1962, cần khoảng n² × 2ⁿ bước, còn phương pháp ngẫu nhiên hóa năm 2010 của Andreas Björklund cần khoảng 1,657ⁿ. Trên thực tế, phép quay lui với cắt tỉa tốt xử lý được đồ thị vài chục đỉnh, và bài toán người chào hàng, vốn tìm chu trình Hamilton ngắn nhất, là phiên bản có trọng số của cùng câu hỏi.
Mã Gray và siêu lập phương
Viết các số từ 0 đến 7 thành mã 3 bit rồi nối hai mã khi chúng khác nhau đúng một bit: kết quả là đồ thị của một khối lập phương. Một chu trình Hamilton trong đó, chẳng hạn 000, 001, 011, 010, 110, 111, 101, 100, liệt kê đủ tám mã sao cho mã nào cũng khác mã liền trước đúng một bit. Danh sách như vậy là một mã Gray, đặt theo tên Frank Gray ở Bell Labs, người mô tả nó trong bằng sáng chế nộp năm 1947. Siêu lập phương nào cũng có một mã như thế: viết các mã ít hơn một bit, rồi viết lại chính danh sách ấy theo chiều ngược, sau đó đặt số 0 trước nửa đầu và số 1 trước nửa sau. Bộ mã hóa vòng quay dùng mã Gray để số đọc được giữa hai vị trí không bao giờ sai quá một bậc. Khối lập phương có 6 chu trình Hamilton còn siêu lập phương 4 bit có 1.344.
Tự khám phá
Hãy mở trình khám phá đường đi Hamilton để tự thử câu đố của Hamilton, với các vòng nét đứt cho thấy bạn có thể đi tiếp đến đâu; hoặc chuyển sang Tìm kiếm và xem phép quay lui làm việc: đường đi lớn dần, nét đứt đỏ đánh dấu chỗ nó quay lui, còn các cột đếm số nút theo chiều dài đường đi. Bật tắt phép kiểm ngõ cụt, phép kiểm liên thông và thứ tự Warnsdorff, so sánh mỗi cách cần bao nhiêu nút, đếm tất cả chu trình của một đồ thị nhỏ, hoặc tự vẽ đồ thị và xem phép thử nhanh nào áp dụng được.
Câu hỏi thường gặp
Đồ thị có mạch Euler thì có phải là đồ thị Hamilton không, hay ngược lại?
Không chiều nào suy ra chiều nào. Nơ bướm, hai tam giác dùng chung một đỉnh, có mạch Euler vì mọi bậc đều chẵn, nhưng không có chu trình Hamilton, bởi đỉnh dùng chung sẽ phải đi qua hai lần. Đồ thị đầy đủ K₄ có chu trình Hamilton, nhưng cả bốn đỉnh đều bậc 3 nên nó không có mạch Euler.
Máy tính không thể cứ thử hết mọi thứ tự sao?
Chỉ với đồ thị nhỏ. Có n! thứ tự của n đỉnh, với 20 đỉnh là khoảng 2,4 × 10¹⁸. Phép quay lui làm tốt hơn nhiều, vì nó chỉ men theo cạnh và bỏ ngay một đường dang dở khi bị tắc: nó tìm đủ 30 chu trình của khối mười hai mặt 20 đỉnh trong khoảng 1.400 bước. Nhưng với một số đồ thị, số đường dang dở vẫn tăng theo cấp số nhân, và chưa có phương pháp nào được biết tránh được điều đó cho mọi đồ thị.
Bài toán đường đi Hamilton có dễ hơn bài toán chu trình không?
Không, cả hai đều NP-đầy đủ. Mỗi bài toán chuyển được thành bài kia: thêm một đỉnh mới nối với mọi đỉnh cũ, thì đồ thị cũ có đường đi Hamilton đúng khi đồ thị mới có chu trình Hamilton. Theo chiều ngược lại, bài toán chu trình thành bài toán đường đi bằng cách thêm một bản sao của một đỉnh, với cùng các đỉnh kề, rồi gắn một đỉnh đầu mút mới vào đỉnh đó và một đỉnh nữa vào bản sao.
Vì sao hành trình quân mã trên bàn 5 × 5 phải bắt đầu ở màu của góc?
Trong 25 ô có 13 ô mang màu của góc và 12 ô mang màu kia, còn quân mã đổi màu sau mỗi nước. Hành trình qua 25 ô luân phiên màu, nên nó bắt đầu và kết thúc ở màu có nhiều ô hơn. Ứng dụng tìm đủ 1.728 hành trình mở của bàn 5 × 5, tức 864 nếu tính một hành trình và chiều ngược của nó là một, và hành trình nào cũng bắt đầu và kết thúc trên ô mang màu của góc.
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.
Mở trình khám phá đường đi Hamilton