Chu trình Euler là gì? Đồ thị Euler, thuật toán và phương trình

Chu trình Euler là một khái niệm quan trọng trong lý thuyết đồ thị, được đặt theo tên nhà toán học Leonhard Euler. Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và quay về đỉnh xuất phát. Bài viết dưới đây sẽ trình bày chi tiết định nghĩa, điều kiện tồn tại, thuật toán tìm chu trình Euler cùng các ví dụ minh họa dễ hiểu.

Chu trình Euler là gì?

Để hiểu rõ chu trình Euler, trước tiên chúng ta cần nắm vững một số khái niệm cơ bản trong lý thuyết đồ thị.

Các khái niệm cơ bản

Định nghĩa chu trình Euler

Chu trình Euler (Eulerian Circuit/Cycle) là một chu trình trong đồ thị thỏa mãn các điều kiện sau:

• Xuất phát từ một đỉnh bất kỳ
• Đi qua tất cả các cạnh của đồ thị
• Mỗi cạnh chỉ được đi qua đúng một lần
• Quay trở về đỉnh xuất phát ban đầu

Đồ thị có chứa chu trình Euler được gọi là đồ thị Euler (Eulerian Graph).

Nguồn gốc lịch sử – Bài toán 7 cây cầu Königsberg

Chu trình Euler bắt nguồn từ bài toán nổi tiếng “7 cây cầu thành phố Königsberg” do Euler giải quyết vào năm 1736:

• Thành phố Königsberg có 4 vùng đất được nối với nhau bởi 7 cây cầu
• Câu hỏi đặt ra: Có thể đi qua tất cả 7 cây cầu, mỗi cầu đúng một lần rồi quay về điểm xuất phát không?
• Euler chứng minh rằng điều này là không thể, từ đó đặt nền móng cho lý thuyết đồ thị

Điều kiện tồn tại chu trình Euler

Không phải đồ thị nào cũng tồn tại chu trình Euler. Dưới đây là các điều kiện cần và đủ để một đồ thị có chu trình Euler.

Định lý Euler cho đồ thị vô hướng

Định lý: Một đồ thị vô hướng liên thông có chu trình Euler khi và chỉ khi:

Tất cả các đỉnh đều có bậc chẵn

Hay nói cách khác:

\[\forall v \in V: \deg(v) \equiv 0 \pmod{2}\]

Điều kiện cho đồ thị có hướng

Với đồ thị có hướng, chu trình Euler tồn tại khi và chỉ khi:

• Đồ thị liên thông yếu (khi bỏ hướng thì liên thông)
• Bậc vào bằng bậc ra tại mọi đỉnh: \(\deg^+(v) = \deg^-(v)\) với mọi đỉnh v

Bảng tóm tắt điều kiện

Phân biệt chu trình Euler và đường đi Euler

Nhiều học sinh thường nhầm lẫn giữa chu trình Euler và đường đi Euler. Dưới đây là bảng so sánh chi tiết.

Đường đi Euler là gì?

Đường đi Euler (Eulerian Path/Trail) là đường đi trong đồ thị:

• Đi qua tất cả các cạnh của đồ thị
• Mỗi cạnh chỉ đi qua đúng một lần
• Không yêu cầu quay về đỉnh xuất phát

Điều kiện tồn tại đường đi Euler

Đồ thị vô hướng liên thông có đường đi Euler khi và chỉ khi:

Có đúng 0 hoặc 2 đỉnh bậc lẻ

• Nếu có 0 đỉnh bậc lẻ → Tồn tại chu trình Euler (đường đi Euler đóng)
• Nếu có 2 đỉnh bậc lẻ → Tồn tại đường đi Euler bắt đầu từ đỉnh bậc lẻ này và kết thúc tại đỉnh bậc lẻ kia

Bảng so sánh chu trình Euler và đường đi Euler

Thuật toán tìm chu trình Euler

Sau khi xác định đồ thị có chu trình Euler, ta cần thuật toán để tìm ra chu trình đó. Dưới đây là hai thuật toán phổ biến nhất.

Thuật toán Fleury

Thuật toán Fleury là thuật toán đơn giản, dễ hiểu để tìm chu trình Euler:

Các bước thực hiện:

1. Bước 1: Chọn một đỉnh bất kỳ làm đỉnh xuất phát
2. Bước 2: Tại mỗi đỉnh, chọn cạnh để đi tiếp theo quy tắc:
   • Ưu tiên chọn cạnh không phải là cầu (cạnh mà nếu xóa đi sẽ làm đồ thị không liên thông)
   • Chỉ chọn cầu khi không còn lựa chọn khác
3. Bước 3: Xóa cạnh vừa đi qua khỏi đồ thị
4. Bước 4: Lặp lại bước 2-3 cho đến khi đi hết tất cả các cạnh

Độ phức tạp: \(O(E^2)\) với E là số cạnh

Thuật toán Hierholzer

Thuật toán Hierholzer hiệu quả hơn thuật toán Fleury:

Các bước thực hiện:

1. Bước 1: Chọn đỉnh xuất phát, tạo một chu trình bất kỳ từ đỉnh đó
2. Bước 2: Nếu còn cạnh chưa đi qua:
   • Tìm đỉnh v trên chu trình hiện tại còn cạnh chưa đi
   • Tạo chu trình mới từ đỉnh v
   • Ghép chu trình mới vào chu trình hiện tại
3. Bước 3: Lặp lại bước 2 cho đến khi đi hết tất cả các cạnh

Độ phức tạp: \(O(E)\) với E là số cạnh

So sánh hai thuật toán

Ứng dụng của chu trình Euler

Chu trình Euler có nhiều ứng dụng quan trọng trong thực tiễn và các lĩnh vực khoa học.

Ứng dụng thực tiễn

• Bài toán người đưa thư (Chinese Postman Problem): Tìm đường đi ngắn nhất để đưa thư qua tất cả các con đường
• Thiết kế mạch điện tử: Vẽ mạch in không có đường dây chồng chéo
• Lập lịch trình: Tối ưu hóa đường đi cho xe quét rác, xe thu gom
• Sinh học phân tử: Giải mã trình tự DNA trong phương pháp giải trình tự de novo

Ứng dụng trong khoa học máy tính

• Mã Gray: Tạo dãy mã nhị phân liên tiếp chỉ khác nhau 1 bit
• Dãy de Bruijn: Tạo dãy chứa tất cả các xâu con độ dài n
• Kiểm tra tính liên thông: Ứng dụng trong phân tích mạng

Ví dụ minh họa và bài tập có lời giải chi tiết

Dưới đây là các ví dụ giúp bạn hiểu rõ hơn về cách xác định và tìm chu trình Euler.

Ví dụ 1: Kiểm tra đồ thị có chu trình Euler

Đề bài: Cho đồ thị G có 4 đỉnh A, B, C, D với các cạnh: AB, AC, AD, BC, BD, CD. Hỏi đồ thị G có chu trình Euler không?

Lời giải:

Tính bậc của mỗi đỉnh:

• deg(A) = 3 (nối với B, C, D)
• deg(B) = 3 (nối với A, C, D)
• deg(C) = 3 (nối với A, B, D)
• deg(D) = 3 (nối với A, B, C)

Nhận xét: Tất cả các đỉnh đều có bậc lẻ (bậc 3).

Kết luận: Đồ thị G KHÔNG có chu trình Euler (vì có đỉnh bậc lẻ).

Tuy nhiên, đồ thị có 4 đỉnh bậc lẻ nên cũng không có đường đi Euler.

Ví dụ 2: Tìm chu trình Euler

Đề bài: Cho đồ thị G có 4 đỉnh A, B, C, D với các cạnh: AB, AD, BC, BD, CD. Kiểm tra và tìm chu trình Euler nếu có.

Lời giải:

Bước 1: Tính bậc của mỗi đỉnh

• deg(A) = 2 (nối với B, D)
• deg(B) = 3 (nối với A, C, D)
• deg(C) = 2 (nối với B, D)
• deg(D) = 3 (nối với A, B, C)

Có 2 đỉnh bậc lẻ (B và D) → Không có chu trình Euler, nhưng có đường đi Euler từ B đến D (hoặc ngược lại).

Bước 2: Tìm đường đi Euler

Xuất phát từ B (đỉnh bậc lẻ):

\[B \rightarrow A \rightarrow D \rightarrow C \rightarrow B \rightarrow D\]

Đường đi Euler: B → A → D → C → B → D

Ví dụ 3: Đồ thị có chu trình Euler

Đề bài: Cho đồ thị G có 4 đỉnh A, B, C, D với các cạnh: AB, BC, CD, DA, AC, BD. Kiểm tra và tìm chu trình Euler.

Lời giải:

Bước 1: Tính bậc của mỗi đỉnh

• deg(A) = 3 (nối với B, C, D)
• deg(B) = 3 (nối với A, C, D)
• deg(C) = 3 (nối với A, B, D)
• deg(D) = 3 (nối với A, B, C)

Tất cả đỉnh đều bậc lẻ → Không có chu trình Euler và không có đường đi Euler.

Ví dụ 4: Đồ thị hình vuông có đường chéo

Đề bài: Cho hình vuông ABCD có cả hai đường chéo AC và BD. Hỏi có thể vẽ hình này bằng một nét vẽ liền (không nhấc bút, mỗi cạnh chỉ vẽ một lần) không?

Lời giải:

Mô hình hóa thành đồ thị với:

• Đỉnh: A, B, C, D và giao điểm O của hai đường chéo
• Cạnh: AB, BC, CD, DA, AO, OC, BO, OD

Tính bậc:

• deg(A) = 3, deg(B) = 3, deg(C) = 3, deg(D) = 3
• deg(O) = 4

Có 4 đỉnh bậc lẻ (A, B, C, D).

Kết luận: Không thể vẽ hình này bằng một nét liền (vì có nhiều hơn 2 đỉnh bậc lẻ).

Ví dụ 5: Áp dụng thuật toán Fleury

Đề bài: Cho đồ thị có 5 đỉnh 1, 2, 3, 4, 5 với các cạnh: (1,2), (2,3), (3,4), (4,5), (5,1), (1,3), (3,5). Tìm chu trình Euler.

Lời giải:

Bước 1: Kiểm tra điều kiện

• deg(1) = 4, deg(2) = 2, deg(3) = 4, deg(4) = 2, deg(5) = 4
• Mọi đỉnh đều có bậc chẵn → Tồn tại chu trình Euler

Bước 2: Áp dụng thuật toán Fleury từ đỉnh 1

\[1 \rightarrow 2 \rightarrow 3 \rightarrow 4 \rightarrow 5 \rightarrow 3 \rightarrow 1 \rightarrow 5 \rightarrow 1\]

(Lưu ý: Có thể có nhiều chu trình Euler khác nhau)

Chu trình Euler: 1 → 2 → 3 → 4 → 5 → 3 → 1 → 5 → 1

Kết luận

Qua bài viết trên, chúng ta đã tìm hiểu chi tiết về chu trình Euler – một khái niệm nền tảng trong lý thuyết đồ thị. Những điểm quan trọng cần ghi nhớ:

• Chu trình Euler là chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần và quay về đỉnh xuất phát
• Điều kiện tồn tại: Đồ thị liên thông và mọi đỉnh đều có bậc chẵn
• Đường đi Euler: Tương tự nhưng không cần quay về đỉnh xuất phát, yêu cầu có 0 hoặc 2 đỉnh bậc lẻ
• Thuật toán tìm: Fleury (đơn giản, \(O(E^2)\)) và Hierholzer (hiệu quả, \(O(E)\))

Việc nắm vững kiến thức về chu trình Euler giúp học sinh giải quyết nhiều bài toán thực tế như tối ưu hóa đường đi, thiết kế mạch điện và các ứng dụng trong khoa học máy tính. Hãy luyện tập thường xuyên với các bài tập để thành thạo kỹ năng phân tích và tìm chu trình Euler.