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.
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
imageanchor="1"
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEglkPNrAbGA_vvKzgFfG_Djkq8mCkeGsFZp13CVixt3l7coxLT25avRpR3d1mP655sfsQgcSPIOQhSSJq__U2NKAulZ5lz8DaH3CTVjVRGbeLGEjQ5qWwlvS8B_6YHG_hDgDWfpsC7Jw_Q/s16000/Euler.png"
/>
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ị
cellpadding="0"
cellspacing="0"
class="tr-caption-container"
style="margin-left: auto; margin-right: auto;"
>
style="margin-left: auto; margin-right: auto;"
>
data-original-height="1000"
data-original-width="1635"
src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEgyWVSBBFevH8zzdj0__lRE1FkjuHeShhp-HdpEBtZ-mZFAo6vb9_F6rShME-0TO2dHN_-HfnJ8Z82aUsas22H7eGwhHrYEwbkr_J6R8LCRkrRJzhOo70YxrW0b4_6WgZ18cyfM4xntHn8/s16000/Hamilton1.png"
/>
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