Đường đi Hamilton

Bách khoa toàn thư mở Wikipedia
Bước tới: menu, tìm kiếm
Đường đi của quân mã trên bàn cờ 3×4 là đường Hamilton.
Các đồ thị 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ề đỉ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 nhà toán học William Rowan Hamilton. [1]

Mục lục

Định nghĩa [sửa]

Các ví dụ [sửa]

Tính chất [sửa]

Định lý Bondy-Chvátal [sửa]

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.

Đị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. [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.

Áp dụng 4 quy tắc tìm đường đi Hamilton [sửa]

  • Cho đồ thị G sau:
    • Hãy tìm ra chu trình Hamilton bằng 4 quy tắc.
Đồ thị G
  • Bài này sẽ chia ra 2 trường hợp:
  • Trường hợp 1: (6 - 11) và (10 - 11): Tức là ta sẽ giữ lại 2 cạnh này. Còn lại 2 cạnh (11 - 9), (11 - 8), (11 - 7) ta sẽ xóa đi.
  • Trường hợp 2: (6 - 11) và (9 - 11): Tức là ta sẽ giữ lại 2 cạnh này. Còn lại 2 cạnh (11 - 10), (11 - 8), (11 - 7) ta sẽ xóa đi.

Trường hợp 1 [sửa]

Đồ thị G
  • Xét đỉnh 7: Theo quy tắc 1
    • Ta thấy đỉnh 7 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Xét đỉnh 10: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 10 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 6: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 6 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 1: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 1 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 4: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 4 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 3: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 3 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 9: Theo quy tắc 1
    • Ta thấy đỉnh 9 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Xét đỉnh 8: Theo quy tắc 1
    • Ta thấy đỉnh 8 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Kết quả: 2 9 4 7 1 10 11 6 5 8 3

Trường hợp 2 [sửa]

Đồ thị G
  • Xét đỉnh 7: Theo quy tắc 1
    • Ta thấy đỉnh 7 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Xét đỉnh 10: Theo quy tắc 1
    • Ta thấy đỉnh 10 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
    • Đồng thời ta thấy ở đỉnh 1 có bậc 4 và đã có 2 cạnh đã được chọn (cạnh màu đỏ). Nên ta loại 2 cạnh còn lại của đỉnh 1 (cạnh màu xanh)
Đồ thị G
  • Xét đỉnh 6: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 6 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 11: Theo quy tắc 1
    • Ta thấy đỉnh 11 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Xét đỉnh 9: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 9 có bậc là 3 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 8: Theo quy tắc 1
    • Ta thấy đỉnh 9 có bậc là 2 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ)
Đồ thị G
  • Xét đỉnh 3: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 3 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 4: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 4 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G
  • Xét đỉnh 1: Theo quy tắc 1 và 3
    • Ta thấy đỉnh 1 có bậc là 4 => Ta sẽ lấy 2 cạnh của nó (cạnh màu đỏ) và loại bỏ cạnh còn lại (quy tắc 3)
Đồ thị G

Kết quả: Ta thấy rằng đỉnh 2 đã bị loại bỏ tất cả các cạnh kề. Trở thành đỉnh cô lập. => Trường hợp này không có đường đi Hamilton

Xem thêm [sửa]

Tham khảo [sửa]

  1. ^ Biggs, N. L. (1981), “T. P. Kirkman, mathematician”, The Bulletin of the London Mathematical Society 13 (2): 97–120, doi:10.1112/blms/13.2.97, MR 608093 .
  2. ^ Graham, p. 20.

Liên kết ngoài [sửa]