Con đường Hamilton

Con đường Hamilton bắt nguồn từ bài toán: 'Từ một đỉnh của khối thập nhị diện đều, di chuyển dọc theo các cạnh của khối đó sao cho đi qua tất cả các đỉnh còn lại đúng một lần rồi trở về điểm xuất phát.' Được đặt theo tên của William Rowan Hamilton vào năm 1859.

Khái niệm

Xét đồ thị G = (V,E) với n đỉnh

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

_n-1, x_n được gọi 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

Chu trình Hamilton

• là một chu trình đi qua mọi đỉnh của đồ thị,

mỗi đỉnh chỉ xuất hiện một lần và kết thúc tại đỉnh ban đầu.

• Đồ thị Hamilton là đồ thị có ít nhất một chu trình và một đường đi Hamilton.
• (G2) Nếu chỉ có đường đi Hamilton thì không có chu trình Hamilton.

Các kết quả liên quan đến đồ thị Hamilton

Khác với đồ thị Euler, hiện tại chưa có một quy tắc đủ và cần để xác định một đồ thị có phải là Hamilton hay không. Các kết quả hiện tại chỉ cung cấp các điều kiện cần thiết để một đồ thị có thể là đồ thị Hamilton hoặc có đường đi Hamilton.

• Đồ thị đủ luôn là đồ thị Hamilton. Nếu n là số lẻ và X1, X2 với |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 với n đỉnh và m cạnh. Nếu m ≥ $({}^{}$
  n 2 − 3 n + 6 ) / 2 {\displaystyle (n^{2}-3n+6)/2} thì G là đồ thị Hamilton.

Các định lý

• Cho đồ thị G với n đỉnh, bao đóng cl(G) được hình thành từ G bằng cách thêm một cạnh mới uv giữa mọi cặp đỉnh không kề nhau u và v với degree(v) + degree(u) ≥ n.
• Dirac (1952) Xem G là đồ thị vô hướng đơn 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.
• Đị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ì đồ thị đầ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.

Một đồ thị đủ là đồ thị Hamilton. Đối với n lẻ ≥ 3, đồ thị đầy đủ Kn (Kn là đồ thị đầy đủ với n đỉnh) có (n-1)/2 chu trình Hamilton đôi một mà không có cạnh chung.

Thuật toán kiểm tra đồ thị Hamilton

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

==> Đây là thuật toán vét cạn, có độ phức tạp cao không thể thực hiện hiệu quả khi n từ 20, 30 đỉnh trở lên.

• Việc phát triển thuật toán hiệu quả để xác định đồ thị Hamilton vẫn là một thách thức lớn đối với các nhà toán học và tin học.
• Nhiều nhà nghiên cứu đã đề xuất các giải pháp như:
• Các thuật toán Heuristic, sử dụng trí tuệ nhân tạo, mạng nơ-ron, thuật toán di truyền, v.v., để giải quyết gần đúng các bài toán về đồ thị Hamilton.
• Các thuật toán này thường có hiệu suất tốt và thường dừng lại ở hai trường hợp sau:

1. Nếu xác định đồ thị đang xem xét là đồ thị Hamilton, đây là một khẳng định chính xác và dễ dàng kiểm tra. 2. Nếu khẳng định rằng đồ thị không phải là Hamilton, có thể xảy ra sai lầm với một xác suất nào đó (thực tế, trường hợp này chính là 'Không biết đồ thị đã cho có phải là đồ thị Hamilton không').

Các quy tắc để xác định chu trình Hamilton

Hiện tại, mặc dù chưa có thuật toán tổng quát, nhưng đã có một số quy tắc khá hiệu quả để tìm kiếm chu trình Hamilton trong đồ thị. Các quy tắc này có thể kết hợp với nhận xét về các đặc điểm đối xứng hoặc tính chất cụ thể của đồ thị để giảm thiểu số lượng trường hợp cần xem xét.

Xem xét đồ thị G=(X,E) với n đỉnh, trong quá trình tìm chu trình Hamilton, chúng ta có thể áp dụng 4 quy tắc sau đây

Quy tắc 1: Loại bỏ tất cả các cạnh kề với đỉnh bậc 2.
Quy tắc 2: Không cho phép xuất hiện chu trình với ít hơn n cạnh.
Quy tắc 3: Nếu đã chọn 2 cạnh kề với đỉnh x, có thể loại bỏ tất cả các cạnh khác kề với x.
Quy tắc 4: Duy trì tính liên thông và đảm bảo rằng bậc của mỗi đỉnh luôn lớn hơn hoặc bằng 2.

Quy tắc 3 được minh họa trong hình, khi áp dụng quy tắc này, bậc của một số đỉnh sẽ giảm xuống, từ đó chúng ta có thể sử dụng 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 trường hợp đặc biệt 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ị, thuộc loại bài toán NP-đầy đủ. Cụ thể, bài toán tìm hành trình đóng của quân mã là một dạng 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ã ở bất kỳ ô nào trên bàn cờ vua, theo quy tắc di chuyển của quân mã, tìm cách di chuyển sao cho mỗi ô chỉ được đi qua một lần và đi hết bàn cờ.

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

Tài liệu tham khảo

• Ore, O 'Một ghi chú về các chu trình Hamilton.' American Mathematical Monthly 67, 55, 1960.
• DeLeon, Melissa, 'Nghiên cứu về các điều kiện đủ cho chu trình Hamilton'. Khoa Toán và Tin học, Đại học Seton Hall
• Hamilton, William Rowan, 'Ghi chép về hệ thống mới của các căn bậc'. Philosophical Magazine, 12 1856
• Hamilton, William Rowan, 'Tổng quan về Giải tích Icosian'. 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 bên ngoài

• Weisstein, Eric W., 'Chu trình Hamilton' từ MathWorld.
• Chu trình Euler và chu trình Hamilton Lưu trữ 2012-03-09 tại Wayback Machine