Đường đi Hamilton

Đường đi của quân mã trên bàn cờ 3×4 là đường Hamilton.

Các đồ thị Hamilton

Trong toán học, ngành lý thuyết đồ thị, một đường đi Hamilton là một đường đi trong đồ thị vô hướng đi qua tất cả các đỉnh của đồ thị, mỗi đỉnh đúng một lần. Một Chu trình Hamilton là một đường đi Hamilton sau đi qua tất cả các đỉnh của đồ thị thì trở về đỉnh xuất phát.

Một đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton, đồ thị có đường đi Hamilton được gọi là đồ thị nửa Hamilton. Bài toán tìm đường đi và chu trình như vậy được gọi là bài toán Hamilton. Bài toán Hamilton là NP đầy đủ. Tên gọi đường đi và chu trình Hamilton là gọi theo tên của nhà toán học William Rowan Hamilton.

Các ví dụ

• Một đồ thị đầy đủ có nhiều hơn hai đỉnh là đồ thị Hamilton.
• Mọi đồ thị vòng là Hamilton.
• Đồ thị khối ba chiều là đồ thị Hamilton

Định lý Bondy-Chvátal

Cho đồ thị G có n đỉnh, bao đóng cl(G) được tạo ra từ G bằng cách bổ sung cho mỗi cặp đỉnh không kề nhau u và v với degree(v) + degree(u) ≥ n một cạnh mới uv.

Định lý Bondy-Chvátal (1972)

Một đồ thị là Hamilton nếu và chỉ nếu bao đóng của nó là Hamilton.

Vì đồ thi đầy đủ là Hamilton, nên tất cả các đồ thị mà bao đóng là đầy đủ là Hamilton.

Dirac (1952)

Một đơn đồ thị n đỉnh (n > 2) là Hamilton nếu mọi đỉnh của nó có bậc không nhỏ hơn n/2.

Ore (1960)

Một đồ thị có n đỉnh (n > 2) là Hamilton nếu tổng các bậc của hai đỉnh không kề nhau đều bằng n hoặc lớn hơn.

Áp dụng 4 quy tắc tìm đường đi Hamilton

• Cho đồ thị G sau:
  • Hãy tìm ra chu trình Hamilton bằng 4 quy tắc.

• Bài này sẽ chia ra 2 trường hợp:
• Trường hợp 1: (6 - 11) và (10 - 11): Tức là ta sẽ giữ lại 2 cạnh này. Còn lại 2 cạnh (11 - 9), (11 - 8), (11 - 7) ta sẽ xóa đi.
• Trường hợp 2: (6 - 11) và (9 - 11): Tức là ta sẽ giữ lại 2 cạnh này. Còn lại 2 cạnh (11 - 10), (11 - 8), (11 - 7) ta sẽ xóa đi.

Trường hợp 1

• Xét đỉnh 7: Theo quy tắc 1
  • Ta thấy đỉnh 7 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Xét đỉnh 10: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 10 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 6: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 6 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 1: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 1 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 4: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 4 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 3: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 3 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 9: Theo quy tắc 1
  • Ta thấy đỉnh 9 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Xét đỉnh 8: Theo quy tắc 1
  • Ta thấy đỉnh 8 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Kết quả: 2 9 4 7 1 10 11 6 5 8 3

Trường hợp 2

• Xét đỉnh 7: Theo quy tắc 1
  • Ta thấy đỉnh 7 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Xét đỉnh 10: Theo quy tắc 1
  • Ta thấy đỉnh 10 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
  • Đồng thời ta thấy ở đỉnh 1 có bậc 4 và đã có 2 cạnh đã được chọn (cạnh màu đỏ). Nên ta loại 2 cạnh còn lại của đỉnh 1 (cạnh màu xanh)

• Xét đỉnh 6: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 6 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 11: Theo quy tắc 1
  • Ta thấy đỉnh 11 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Xét đỉnh 9: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 9 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 8: Theo quy tắc 1
  • Ta thấy đỉnh 9 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)

• Xét đỉnh 3: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 3 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 4: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 4 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

• Xét đỉnh 1: Theo quy tắc 1 và 3
  • Ta thấy đỉnh 1 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)

Kết quả: Ta thấy rằng đỉnh 2 đã bị loại bỏ tất cả các cạnh kề. Trở thành đỉnh cô lập. => Trường hợp này không có đường đi Hamilton

Xem thêm

• Chu trình Euler.
• Thuật ngữ lý thuyết đồ thị
• Định lý Dirac

Tham khảo

• Ore, O "A Note on Hamiltonian Circuits." American Mathematical Monthly 67, 55, 1960.
• DeLeon, Melissa, "A Study of Sufficient Conditions for Hamiltonian Cycles". Department of Mathematics and Computer Science, Seton Hall University
• Hamilton, William Rowan, "Memorandum respecting a new system of roots of unity". Philosophical Magazine, 12 1856
• Hamilton, William Rowan, "Account of the Icosian Calculus". Proceedings of the Royal Irish Academy, 6 1858

Liên kết ngoài

• The Hamiltonian Page - Hamiltonian cycle and path problems, their generalizations and variations.
• Weisstein, Eric W., "Hamiltonian Circuit" từ MathWorld.