Bài toan Hamilton

Bài toán đường đi Hamilton
I.- Khái niệm
Trong toán học, đôi khi găp khái niệm “Chu trình Hamilton hoặc đường đi Hamilton” hoặc “Bài toán Hamilton” với các môn / ngành lý thuyết đồ thị làm chúng ta phân vân. Tài liệu này giới thiệu sơ lược về thuật ngữ đó và vài vấn đề liên quan.
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 .
II.-Các ví dụ :
1./ Đường đi của quân mã trên bàn cờ 3×4 là đường Hamilton.



2./ 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




III.-Đị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.
IV.- Đị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.
V.- 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.
VI.- 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.


( Theo nguồn Bách khoa toàn thư mở Wikipedia )