Đường đi Hamilton

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm

Đườ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

Định nghĩa[sửa | sửa mã nguồn]

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

Đường đi x0,x1,...,xn-1,xnđường đi Hamilton nếu V = {x0,x1,...,xn-1,xn} xi!=xj , 0 ≤ i < j ≤ n

Chu trình x0,x1,...,xn,x0chu trình Hamilton nếu x0,x1,...,xn,x0 là đường đi Hamilton

  • Dây chuyền Hamilton là dây chuyền đi qua các đỉnh của đồ thị và đi qua mỗi đỉnh đúng 1 lần.
  • Chu trình Hamilton là dây chuyền Hamilton xuất phát từ mộ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 một chu trình Hamilton.

Ví dụ[sửa | sửa mã nguồn]

  • (G1) Là đồ thị Hamilton (nên đương nhiên có chu trình và dây chuyền Hamilton).
  • (G2) Chỉ có dây chuyền Hamilton nên không phải là đồ thị Hamilton (và được gọi là đồ thị nữa Hamilton).
  • (G3) Không có dây chuyền lẫn chu trình Hamilton nên không phải là đồ thị Hamilton.

- Một vài ví dụ về đồ thị Hamilton

Ví dụ đồ thị Hamilton

Một số kết quả liên quan đến đồ thị Hamilton[sửa | sửa mã nguồn]

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ó dây chuyền Hamilton.

  • Đồ thị đủ luôn là đồ thị Hamilton. Với n lẻ và n ≥ 3 thì Kn có (n-1)/2 chu trình Hamilton đôi một không có cạnh chung.
  • Giả sử G là đồ thị phân đôi với hai tập đỉnh 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/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ó dây chuyền 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 ≥ (n^2-3n+6)/2 thì G là đồ thị Hamilton.

Định lý[sửa | sửa mã nguồn]

  • Cho đồ thị Gn đỉ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 uv với degree(v) + degree(u) ≥ n một cạnh mới uv.
  • Dirac (1952) Xét G là đơn đồ thị vô hướngvới n đỉnh (n ≥ 3). Nếu d(x) ≥ n/2 với mọi đỉnh x của G thì G là đồ thị Hamilton.
  • 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.
  • Đị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[sửa | sửa mã nguồn]

  • Hiện nay chưa có các qui tắc cần và đủ để kiểm tra xem một đồ thị có là Hamilton hay không, nên các nhà nghiên cứu hạ yêu cầu xuống là: Hãy đề xuất một thuật toán để xác định xem một đồ thị bất kì có phải là đồ thị Hamilton hay không.
  • Giả sử G=(X,E)đồ thị vô hướng gồm n đỉnh với tập đỉnh X={x1,x2,...,xn}, nếu G là đồ thị Hamilton thì sẽ có chu trình Hamilton có dạng: x1--xi1--xi2--xi3... xi n-1--x1,với {i1,i2,...,in-1} là một hoán vị của tập hợp {2,3,...,n}

==> Từ đó, ta có một thuật toán hiển nhiên là: Đặt Z={xi1, xi2, xi3,…} 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.

  • Cho đến nay, việc nghiên cứu tìm ra 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").

Qui tắc để tìm chu trình Hamilton[sửa | sửa mã nguồn]

Hiện nay, dù chưa tìm ra thuật toán tổng quát, nhưng có một số qui tắc khá tốt để sử dụng trong quá trình tìm chu trình Hamilton trong đồ thị. Những qui 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 qui tắc[2] sau đây

Qui tắc 1: Lấy hết các cạnh kề với đỉnh bậc 2.
Qui tắc 2: Không cho phát sinh chu trình ít hơn n cạnh.
Qui 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.
Qui 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.
Hamilton QT.png

Quy tắc 3 được minh họa trong hình,khi thực hiện qui 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 qui tắc 1 và qui tắc 4.

Ứng dụng[sửa | sửa mã nguồn]

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ờ 5x5 - Đặt một quân mã ở 1 ô 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[sửa | sửa mã nguồn]

Tham khảo[sửa | sửa mã nguồn]

  1. ^ Gardner, M. "Mathematical Games: About the Remarkable Similarity between the Icosian Game and the Towers of Hanoi." Sci. Amer. 196, 150-156, May 1957
  2. ^ 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[sửa | sửa mã nguồn]

  • Đường đi Euler và Hamilton (Euler & Hamilton Paths), TS. Trần Văn Hoài, "[1]".

Liên kết ngoài[sửa | sửa mã nguồn]