Đường đi Hamilton có nguồn gốc từ bài toán: Xuất phát từ một đỉnh của khối thập nhị diện đều hãy đi dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh khác, mỗi đỉnh đúng một lần sau đó quay về đỉnh xuất phát.
Bài viết hoặc đoạn này cần được wiki hóa để đáp ứng tiêu chuẩn quy cách định dạng và văn phong của Wikipedia. |
Bài viết hoặc đoạn này cần người am hiểu về chủ đề này trợ giúp biên tập mở rộng hoặc cải thiện. |
Cho đồ thị G = (V,E), có n đỉnh
Đường đi x0,x1,...,x
n-1,xn là đường đi Hamilton nếu V = {x0,x1,...,xn-1,xn} xi!=xj , 0 ≤ i < j ≤ n
Chu trình x0,x1,...,x
Hamilton
mỗi đỉnh đúng một lần và quay trở về nơi xuất phát.
Không giống như đồ thị Euler, hiện nay chưa có quy tắc cần và đủ để kiểm tra xem một đồ thị có là Hamilton không. Các kết quả có được hiện nay chỉ là các điều kiện đủ để một đồ thị là đồ thị Hamilton hay có đường đi Hamilton.
Đồ thị đủ luồn là đồ thị Hamilton, với n lẻ ≥ 3 thì Kn(Kn là đồ thị đủ với n đỉnh) có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung.
==> Đây là một thuật toán vét cạn, có độ phức tạp không khả thi khi n chỉ từ 20,30 đỉnh trở lên.
1. Nếu khẳng định đồ thị đang xét là đồ thị Hamilton là đó là một khẳng định chính xác và có thể kiểm chứng dễ dàng. 2. Nếu khẳng định định không phải là đồ thị Hamilton: có thể bị sai lầm với một xác suất nào đó(thật ra trường hợp này chính là "Không biết đồ thị đã cho có phải là đồ thị Hamilton không").
Hiện nay, dù chưa tìm ra thuật toán tổng quát, nhưng có một số quy tắc khá tốt để sử dụng trong quá trình tìm chu trình Hamilton trong đồ thị. Những quy tắc này có thể phối hợp với nhận xét về các tính chất đối xứng hay về tính chất nào đó của một đồ thị cụ thể để khỏi phải xét nhiều trường hợp khác nhau.
Xét đồ thị G=(X,E) gồm n đỉnh, trong quá trình tìm chu trình Hamilton chúng ta có thể vận dụng 4 quy tắc sau đây
Quy tắc 1: Lấy hết các cạnh kề với đỉnh bậc 2. Quy tắc 2: Không cho phát sinh chu trình ít hơn n cạnh. Quy tắc 3: Nếu đã lấy 2 cạnh kề với đỉnh x thì có thể bỏ tất cả các cạnh còn lại kề với x. Quy tắc 4: Duy trì tính liên thông và bảo đảm bậc mỗi đỉnh luôn lớn hơn hay bằng 2.
Quy tắc 3 được minh họa trong hình,khi thực hiện quy tắc này thì bậc của một số đỉnh bị giảm xuống: nhờ vậy chúng ta có thể tận dụng trở lại quy tắc 1 và quy tắc 4.
Bài toán mã đi tuần là một dạng của bài toán tổng quát hơn là bài toán tìm đường đi Hamilton trong lý thuyết đồ thị, là một bài toán NP-đầy đủ. Bài toán tìm hành trình đóng của quân mã là một bài toán cụ thể của bài toán tìm chu trình Hamiltonian.
Bài toán mã đi tuần trên bàn cờ
- Đặt một quân mã ở một ô bất kì trên bàn cờ vua, theo quy tắc di chuyển của cờ vua, tìm các bước đi của quân mã sao cho mỗi ô chỉ được đi qua 1 lần và đi hết bàn cờ.
Wiki Commons có thêm hình ảnh và phương tiện truyền tải về Đường đi Hamilton. |
This article uses material from the Wikipedia Tiếng Việt article Đường đi Hamilton, which is released under the Creative Commons Attribution-ShareAlike 3.0 license ("CC BY-SA 3.0"); additional terms may apply (view authors). Nội dung được phát hành theo CC BY-SA 4.0, ngoại trừ khi có ghi chú khác. Images, videos and audio are available under their respective licenses.
®Wikipedia is a registered trademark of the Wiki Foundation, Inc. Wiki Tiếng Việt (DUHOCTRUNGQUOC.VN) is an independent company and has no affiliation with Wiki Foundation.