Đường đi 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 William Rowan Hamilton .

Các ví dụ

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

Các đồ thị Hamilton

• 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.

Xem thêm

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

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.

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