Đườ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ề ...
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 .
Đường đi của quân mã trên bàn cờ 3×4 là đường 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
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.
Các đồ thị Hamilton
Đị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.
