Đường đi Hamilton

Đườ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." là gọi theo tên của William Rowan Hamilton phát biểu vào năm 1859.

Khối thập nhị diện đều

Đường đi Hamilton

Ba ví dụ trên biểu đồ lưới 8x8

Định nghĩa

Cho đồ thị G = (V,E), có n đỉnh

Đường đi x₀,x₁,...,x

_n-1,x_n là đường đi Hamilton nếu V = {x₀,x₁,...,x_n-1,x_n} x_i!=x_j , 0 ≤ i < j ≤ n

Chu trình x₀,x₁,...,x

Hamilton

• t đỉnh, đi qua tất cả các đỉnh khác của đồ thị,

mỗi đỉnh đúng một lần và quay trở về nơi xuất phát.

• Đồ thị Hamilton là đồ thị có chứa ít nhất hai đỉnh là chu trình và đường đi Hamilton).
• (G2) Chỉ có đường đi Hamilton nên không

Ví dụ đồ thị Hamilton

Một số kết quả liên quan đến đồ thị Hamilton

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ẻ và X1, X2 và |X1| = |X2| = n. Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton.
• Giả sử G là đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3. Nếu d(x) ≥ (n-1)/2 với mọi đỉnh x của G thì G có đường đi Hamilton.
• Giả sử G là đồ thị vô hướng đơn gồm n đỉnh với n ≥ 3. Nếu d(x) + d(y) ≥ n với mọi cặp đỉnh x,y không kề nhau của G thì G là đồ thị Hamilton.
• Giả sử G là đồ thị vô hướng đơn gồm n đỉnh và m cạnh. Nếu m ≥ ${\displaystyle (n^{2}-3n+6)/2}$ thì G là đồ thị Hamilton.

Định lý

• 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.
• Dirac (1952) Xét G là đơn đồ thị vô hướng 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.
• Đị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 đầy đủ là Hamilton.
• Ghouila-Houiri (1960) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu mọi đỉnh có bậc ≥ n
• Meyniel(1973) Một đồ thị liên thông mạnh với n đỉnh là đồ thị Hamilton nếu d(x)+d(y) ≥ 2n-1 với mọi cặp đỉnh x,y không kề nhau.

Đồ 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.

Thuật toán xác định đồ thị Hamilton

• Giả sử G=(X,E) là đồ thị vô hướng gồm n đỉnh với tập đỉnh X={x₁,x₂,...,x_n}, nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng: x₁--x_i1--x_i2--x_i3... x_{i n-1}--x₁,với {i₁,i₂,...,i_n-1} là một hoán vị của tập hợp {2 hiên là: Đặt Z={x_i1, x_i2, x_i3,…} là dãy đỉnh tương ứng trong hoán vị của tập {2,3,…n}ta kiểm tra xem Z có tạo nên chu trình hay không, tức là phải kiểm tra (n-1)! tập (Z) khác nhau.

==> Đâ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.

• Thuật toán hiệu quả, xác định xem một đồ thị Hamilton hay không vẫn đang là một thách thức lớn đối với các nhà toán học và tin học.
• Một số nhà nghiên cứu đã đề xuất
• Các thuật toán Heuristic (nhờ vào việc vận dụng các thuật toán thông minh nhân tạo, mạng neural, thuật toán gen,...) để giải quyết gần đúng các bài toán Hamilton.
• Những thuật toán loại này khá nhanh và thông thường dừng với hai trường hợp sau:

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").

Quy tắc để tìm chu trình Hamilton

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^[1] 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.

Ứng dụng

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

Mã đi tuần

Xem thêm

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

Tham khảo

1. Trần Đan Thư - Dương Anh Đức, Lý Thuyết Đồ Thị, Đại Học Khoa Học Tự Nhiên - ĐHQGTP.HCM, tháng 9, năm 2008

Tài liệu

• 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

• Đường đi Euler và Hamilton (Euler & Hamilton Paths), TS. Trần Văn Hoài, "[1] Lưu trữ 2013-06-26 tại Wayback Machine".

Liên kết ngoài

• Weisstein, Eric W., "Hamiltonian Cycle" từ MathWorld.
• Euler tour and Hamilton cycles Lưu trữ 2012-03-09 tại Wayback Machine