| Định nghĩa |
Một chu trình trong đồ thị đi qua mỗi cạnh đúng một lần và trở về điểm xuất phát. |
Một đường đi trong đồ thị đi qua mỗi cạnh đúng một lần. |
| Điều kiện tồn tại |
Đồ thị phải liên thông và mỗi đỉnh có bậc chẵn. |
Đồ thị phải liên thông và có đúng 0 hoặc 2 đỉnh có bậc lẻ. |
| Liên quan đến đỉnh |
Trở lại điểm xuất phát, tức là đi qua tất cả các đỉnh theo một chu trình kín. |
Không cần trở lại điểm xuất phát. Có thể có điểm bắt đầu và điểm kết thúc khác nhau. |
| Ứng dụng |
Sử dụng trong các vấn đề cần quay lại điểm xuất phát sau khi đi qua tất cả các cạnh, ví dụ như vấn đề tìm đường đi qua các cây cầu của Königsberg. |
Sử dụng trong các vấn đề cần đi qua tất cả các cạnh mà không cần quay lại điểm xuất phát, ví dụ như vấn đề vẽ đường mà không cần nhấc bút lên. |
| Tính khả thi |
Tồn tại khi đồ thị có bậc của tất cả các đỉnh đều chẵn. |
Tồn tại khi đồ thị có bậc của tất cả các đỉnh đều chẵn hoặc có đúng hai đỉnh có bậc lẻ. |
| Ví dụ điển hình |
Đồ thị Euler trong vấn đề cây cầu Königsberg (tổng bậc các đỉnh lẻ khác 2). |
Đường đi Euler trong việc vẽ một hình không nhấc bút lên và không vẽ lại đường cũ. |
| Bậc của các đỉnh |
Tất cả các đỉnh phải có bậc chẵn. |
Có thể có 0 hoặc 2 đỉnh có bậc lẻ. |
| Liên thông |
Đồ thị phải liên thông mạnh (strongly connected). |
Đồ thị phải liên thông yếu (weakly connected). |
| Thuật toán phổ biến
|
Fleury, Hierholzer
|
Fleury, Hierholzer
|
| Độ phức tạp thời gian với ma trận kề
|
O(V^2), với V là số đỉnh.
|
O(V^2), với V là số đỉnh.
|
| Độ phức tạp không gian
|
O(V + E), với V là số đỉnh và E là số cạnh.
|
O(V + E), với V là số đỉnh và E là số cạnh.
|
| Độ phức tạp dữ liệu
|
O(E), với E là số cạnh.
|
O(E), với E là số cạnh.
|