Giới thiệu Euler, Hamilton
Chu trình Euler và chu trình Hamilton là hai khái niệm quan trọng trong lý thuyết đồ thị, nhưng chúng có những điểm khác biệt cơ bản.
Chu trình Euler:
- Định nghĩa: Chu trình Euler trong một đồ thị vô hướng là một chu trình đi qua mỗi cạnh đúng một lần.
- Điều kiện tồn tại: Một đồ thị liên thông (trong đó có thể đi từ bất kỳ đỉnh nào đến bất kỳ đỉnh nào khác) có chu trình Euler nếu và chỉ nếu tất cả các đỉnh của nó đều có bậc chẵn.
- Ứng dụng: Chu trình Euler thường được sử dụng trong các bài toán như tìm đường đi qua tất cả các đường phố trong một thành phố một lần, ví dụ như bài toán "Người đưa thư" (postman problem).
Chu trình Hamilton:
- Định nghĩa: Chu trình Hamilton trong một đồ thị là một chu trình đi qua mỗi đỉnh đúng một lần.
- Điều kiện tồn tại: Không có tiêu chuẩn đơn giản để xác định liệu một đồ thị có chu trình Hamilton hay không, và việc tìm kiếm một chu trình Hamilton trong một đồ thị là một bài toán NP-đầy đủ.
- Ứng dụng: Chu trình Hamilton thường được áp dụng trong các bài toán như bài toán "Người du lịch" (travelling salesman problem), nơi cần tìm một đường đi ngắn nhất qua tất cả các thành phố một lần và quay lại điểm xuất phát.
So sánh chi tiết:
| Tiêu chí | Chu trình Euler | Chu trình Hamilton |
|---|---|---|
| Định nghĩa | Đi qua mỗi cạnh một lần | Đi qua mỗi đỉnh một lần |
| Điều kiện tồn tại | Đồ thị liên thông và tất cả các đỉnh có bậc chẵn | Không có tiêu chuẩn đơn giản, bài toán NP-đầy đủ |
| Loại đồ thị | Đồ thị vô hướng và có thể áp dụng cho đồ thị có hướng | Đồ thị vô hướng và có thể áp dụng cho đồ thị có hướng |
| Độ phức tạp tìm kiếm | O(E) với thuật toán Hierholzer, O(V + E) với thuật toán Fleury | NP-đầy đủ |
| Độ phức tạp không gian | O(V + E) với thuật toán Hierholzer, O(V) với thuật toán Fleury | O(V) (không gian của các đỉnh) |
| Độ phức tạp dữ liệu | Yêu cầu lưu trữ danh sách cạnh và đỉnh | Yêu cầu lưu trữ danh sách đỉnh và đường đi giữa các đỉnh |
| Ứng dụng | Tìm đường đi qua tất cả các cạnh (ví dụ: bài toán người đưa thư) | Tìm đường đi qua tất cả các đỉnh (ví dụ: bài toán người du lịch) |
| Ví dụ điển hình | Bài toán 7 cây cầu Königsberg | Bài toán người du lịch |
| Đặc điểm chính | Có thể quay lại đỉnh bắt đầu sau khi đi qua tất cả các cạnh | Phải quay lại đỉnh bắt đầu sau khi đi qua tất cả các đỉnh |
| Cách tìm kiếm | Dễ dàng hơn với các thuật toán như Fleury hoặc Hierholzer | Khó hơn và thường dùng các thuật toán heuristic hoặc backtracking |