Thuật Toán Tìm Chu Trình Euler Trong Đồ Thị Vô Hướng

Thuật Toán Tìm Chu Trình Euler

Hello các bạn. Hôm nọ mình có đăng một bài về chu trình Hamilton, thấy có vẻ view khá ổn nên hôm nay mình lại đăng thêm tiếp một bài về thuật toán nữa.

Thuật Toán Tìm Chu Trình Euler Trong Đồ Thị Vô Hướng

Thịt chó thì phải có mắm tôm mà nhắc đến chu trình Hamilton không thể không nhắc đến chu trình Euler. Hai chu trình mà dù các bạn học ở bất cứ môn nào thì chúng luôn luôn được dạy cùng nhau. Và cụ thể như thế nào thì chúng ta sẽ tìm hiểu kĩ hơn ở bên dưới!

Tìm Hiểu Thuật Toán:

Vì Sao Nó Có Tên Là Chu Trình Euler?

• Chu trình Euler hay đường đi Euler xuất phát từ bài toán bảy cây cầu do Euler giải quyết vào khoảng năm 1737.
• Bài toán: Thành phố Konigsberg - Đức có 2 vùng bị ngăn cách bởi một dòng sông và có 2 đảo ở giữa sông. Có 7 chiếc cầu nối những vùng này với nhau. Người dân trong vùng thách đố nhau là thử tìm cách xuất phát từ một vùng đi dạo qua mỗi chiếc cầu đúng một lần và trở về nơi xuất phát.
• Carl Hierholzer là người đầu tiên mô tả hoàn chỉnh đồ thị Euler vào năm 1873.

Chu Trình Euler Khác Chu Trình Hamilton Ở Điểm Nào?

• Chu trình Hamilton là chu trình đi qua tất cả các đỉnh, mỗi đỉnh đúng 1 lần (trừ đỉnh xuất phát).
• Còn chu trình Euler là chu trình đi qua tất cả các cạnh, mỗi cạnh đúng 1 lần.

Định lí:

• Đồ thị vô hướng là đồ thị Euler khi và chỉ khi nó là đồ thị liên thông trong đó các đỉnh có bậc là số chẵn

Mô Tả Thuật Toán:

• Thuật toán tìm chu trình Euler được giải bằng ngăn xếp với ngôn ngữ C++.
• Đầu vào là đồ thị vô hướng vó n đỉnh và m cạnh. Danh sách đỉnh kề adj được khai báo dưới dạng vector<list> với adj[i] là danh sách đỉnh kề của đỉnh i.
• stack<int> S lưu danh sách đề cử các đỉnh.
• vector<int> E là mô hình hóa chu trình Euler.
• Thuật toán bắt đầu từ một đỉnh bất kì trên đồ thị vô hướng gọi là đỉnh v, S.push(v) - thêm v vào danh sách đề cử.
• Ta sẽ chạy một vòng lặp while cho đến khi danh sách đề cử S không còn đỉnh nào.
• Bên trong hàm while được mô tả như sau:
• Lấy ra đỉnh trên cùng của S, ta tạm gọi là đỉnh x.
• Kiểm tra danh sách đỉnh kề adj[x].
• Nếu danh sách kề của x khác rỗng, ta chọn một đỉnh y bất kì thuộc adj[x] rồi thêm vào S. Xóa cạnh xy ra khỏi đồ thị và tiếp tục thực hiện vòng lặp.
• Ngược lại nếu danh sách kề của x là rỗng tức là các cạnh kề của x đều đã đi qua thì ta xóa x ra khỏi S và thêm x vào E.
• Việc này lặp đi lặp lại đến khi S không còn một phần tử nào - tất cả các đỉnh đều đã được đi qua đúng một lần.
• E sau cùng ta có được chính là mô hình hóa của chu trình Euler.

Mã Nguồn:

Code mình viết dựa trên mô tả thuật toán bên trên, bắt đầu từ đỉnh v = 1 và lấy y là đỉnh đầu tiên trong danh sách kề.

Ví Dụ:

Mình vẫn sẽ lấy ví dụ của bài Hamilton cho các bạn dễ hình dung cũng như có thể so sánh sự khác nhau giữa 2 chu trình.

Đồ Thị

Đồ Thị Vô Hướng

Input:

Đầu vào vẫn như bài trước.

• 7 12
• 1 3
• 1 6
• 2 4
• 2 5
• 2 6
• 2 7
• 3 4
• 3 6
• 3 7
• 4 5
• 4 7
• 6 7

Output:

Một đồ thị có thể có nhiều chu trình Euler, nhưng bài này mình giải theo code bên trên nên chỉ ra một chu trình như bên dưới thôi.

• 1 6 7 3 6 2 7 4 5 2 4 3 1

Lời Kết

Trên đây là những chia sẻ của mình về cách tìm chu trình Euler. Tất cả chỉ dựa trên những gì mình học và mình hiểu, nếu có sai sót ở đâu hoặc các bạn muốn mình làm tiếp về thuật toán nào thì hãy để lại comment ở bên dưới cho mình biết nhé!

Copyright © Phạm Văn Linh