Tìm hiểu chu trình Euler từ bài toán bảy cây cầu đến ứng dụng thực tiễn

Chu trình Euler không chỉ là một khái niệm lý thuyết mà còn có nhiều ứng dụng thực tế, từ việc tối ưu hóa lộ trình giao hàng, thu gom rác, đến thiết kế mạng lưới viễn thông và kiểm tra bo mạch điện tử. Bằng cách tìm ra một đường đi qua tất cả các cạnh của đồ thị mà không lặp lại, chúng ta có thể giải quyết nhiều vấn đề tối ưu hóa phức tạp. Việc hiểu rõ chu trình Euler sẽ mở ra một góc nhìn mới về cách giải quyết các bài toán logic và tối ưu trong khoa học máy tính và đời sống.

Nguồn gốc từ bài toán 7 cây cầu Königsberg

Lý thuyết đồ thị ra đời vào thế kỷ 18 với bài báo của Leonhard Euler giải quyết bài toán nổi tiếng về 7 cây cầu ở thành phố Königsberg, Đức (nay là Kaliningrad, Nga). Thành phố được chia làm 4 vùng bởi các nhánh sông Pregel, và 7 cây cầu được xây để nối các vùng này. Người dân đặt câu hỏi liệu có thể xuất phát từ một điểm, đi qua mỗi cây cầu đúng một lần rồi quay về điểm xuất phát hay không.

Euler đã mô hình hóa bài toán bằng cách biểu diễn 4 vùng đất thành 4 đỉnh và 7 cây cầu thành 7 cạnh nối các đỉnh, tạo thành một đa đồ thị. Bài toán trở thành: "Có tồn tại một chu trình đi qua tất cả các cạnh của đồ thị, mỗi cạnh đúng một lần không?". Euler đã chứng minh rằng điều này là không thể. Công trình của ông đã khai sinh ra một nhánh mới của toán học - lý thuyết đồ thị, và chu trình đi qua tất cả các cạnh đúng một lần được đặt tên là chu trình Euler để vinh danh ông.

Các khái niệm và định lý cơ bản

Trước khi đi vào thuật toán, chúng ta cần nắm vững một số khái niệm và định lý quan trọng:

Chu trình Euler: Là một chu trình đơn (không lặp lại đỉnh, trừ điểm đầu và cuối) chứa tất cả các cạnh của đồ thị.
Đường đi Euler: Là một đường đi đơn chứa tất cả các cạnh của đồ thị.
Đồ thị Euler: Là một đồ thị có chu trình Euler.
Đồ thị nửa Euler: Là một đồ thị có đường đi Euler nhưng không có chu trình Euler.

Định lý và hệ quả cho đồ thị vô hướng

Định lý 1: Một đồ thị vô hướng liên thông G có chu trình Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn (số cạnh nối vào mỗi đỉnh là số chẵn).

Chứng minh: Khi đi dọc theo một chu trình Euler, mỗi lần đi vào và đi ra một đỉnh, ta sử dụng hai cạnh. Vì chu trình đi qua tất cả các cạnh, mỗi đỉnh phải có một số cạnh là bội của 2, tức là bậc chẵn. Ngược lại, nếu mọi đỉnh đều có bậc chẵn, ta có thể xây dựng được một chu trình Euler.

Hệ quả 1: Một đồ thị vô hướng liên thông G có đường đi Euler khi và chỉ khi nó có đúng 2 đỉnh bậc lẻ. Hai đỉnh bậc lẻ này chính là điểm bắt đầu và kết thúc của đường đi.

Chứng minh: Nếu ta thêm một cạnh "giả" nối hai đỉnh bậc lẻ này, đồ thị mới sẽ có tất cả các đỉnh bậc chẵn và do đó có một chu trình Euler. Khi loại bỏ cạnh giả, chu trình đó trở thành một đường đi Euler.

Định lý và hệ quả cho đồ thị có hướng

Định lý 2: Một đồ thị có hướng liên thông yếu có chu trình Euler khi và chỉ khi mọi đỉnh của nó có bán bậc vào bằng bán bậc ra (số cạnh đi vào bằng số cạnh đi ra).

Hệ quả 2: Một đồ thị có hướng liên thông yếu có đường đi Euler khi và chỉ khi có đúng hai đỉnh đặc biệt: một đỉnh bắt đầu s với bán bậc ra = bán bậc vào + 1 và một đỉnh kết thúc t với bán bậc vào = bán bậc ra + 1. Các đỉnh còn lại đều có bán bậc vào bằng bán bậc ra.

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

Dựa trên các định lý trên, thuật toán Fleury được phát triển để tìm chu trình Euler trong một đồ thị. Ý tưởng của thuật toán khá đơn giản: xuất phát từ một đỉnh, đi qua các cạnh của đồ thị và xóa chúng sau khi đi qua, tuân theo một quy tắc ưu tiên.

Phát biểu bài toán

Cho một đa đồ thị vô hướng, liên thông G. Hãy tìm một chu trình Euler của đồ thị đó.

Input:

- Dòng đầu tiên chứa số nguyên dương n (1 ≤ n ≤ 100), biểu thị số lượng đỉnh của đồ thị.

- Các dòng tiếp theo, mỗi dòng gồm ba số nguyên u, v, k. Điều này có nghĩa là giữa hai đỉnh u và v tồn tại k cạnh nối với nhau.

Output:

- In ra một chu trình Euler của đồ thị nếu tồn tại.

- Nếu đồ thị không phải là đồ thị Euler, hãy in ra 0.

Ví dụ:

Input mẫu:

1 2 1

1 3 2

1 4 1

2 3 1

3 4 1

Output mẫu:

1 2 3 1 3 4 1

Ý tưởng thuật toán Fleury

Thuật toán hoạt động dựa trên hai nguyên tắc chính:

Xóa cạnh đã đi qua: Sau khi di chuyển qua một cạnh, xóa nó khỏi đồ thị để đảm bảo không đi lại lần thứ hai.
Ưu tiên cạnh không phải là cầu: Chỉ chọn đi vào một cạnh "cầu" (cạnh mà nếu xóa đi sẽ làm tăng số thành phần liên thông của đồ thị) nếu không còn lựa chọn nào khác. Cạnh "cầu" còn được gọi là cạnh "một đi không trở lại".

Để kiểm tra một cạnh (u, v) có phải là cầu hay không, ta có thể thử xóa nó đi rồi dùng thuật toán tìm kiếm như BFS (Breadth-First Search) hoặc DFS (Depth-First Search) để xem có còn đường đi từ v về u hay không. Nếu không, đó chính là một cạnh cầu.

Cải tiến thuật toán Fleury với ngăn xếp (Stack)

Phiên bản cơ sở của thuật toán Fleury có thể không hiệu quả vì phải kiểm tra tính chất "cầu" của cạnh ở mỗi bước. Một cải tiến phổ biến là sử dụng ngăn xếp để xây dựng chu trình.

Ý tưởng:

Bắt đầu từ một đỉnh u bất kỳ, đẩy u vào ngăn xếp.
Khi ngăn xếp chưa rỗng, lấy đỉnh v ở đỉnh ngăn xếp.
Nếu v còn cạnh kề chưa được duyệt, chọn một cạnh (v, w), xóa cạnh đó, đẩy w vào ngăn xếp và lặp lại từ đỉnh w.
Nếu v không còn cạnh kề nào, điều này có nghĩa là ta đã hoàn thành một chu trình con quay về v. Lấy v ra khỏi ngăn xếp và thêm vào kết quả chu trình Euler.
Lặp lại cho đến khi ngăn xếp rỗng.

Kết quả cuối cùng sẽ là một chu trình Euler của đồ thị. Vì các đỉnh được thêm vào kết quả khi chúng không còn cạnh để đi, chuỗi kết quả cần được đảo ngược để có thứ tự đúng của chu trình.

Ví dụ cài đặt (C++):

cpp

#include <iostream>

#include <vector>

#include <stack>

#include <numeric>

#include <algorithm>

using namespace std;

// Hàm kiểm tra đồ thị có phải là đồ thị Euler không

bool isEulerian(int n, const vector<vector<int>>& adj) {

// Kiểm tra tính liên thông và bậc của các đỉnh

// ... (Phần code này có thể tham khảo từ bài viết gốc)

return true; // Giả sử đồ thị là Euler để đơn giản hóa ví dụ

}

// Thuật toán Fleury cải tiến với stack

void findEulerCircuit(int n, vector<vector<int>>& adj) {

if (!isEulerian(n, adj)) {

cout << "Đồ thị không phải là đồ thị Euler." << endl;

return;

}

stack<int> s;

vector<int> circuit;

s.push(0); // Bắt đầu từ đỉnh 0

while (!s.empty()) {

int u = s.top();

bool foundEdge = false;

for (int v = 0; v < n; ++v) {

if (adj[u][v] > 0) {

s.push(v);

adj[u][v]--;

adj[v][u]--;

foundEdge = true;

break;

}

if (!foundEdge) {

circuit.push_back(u);

s.pop();

}

reverse(circuit.begin(), circuit.end());

cout << "Chu trình Euler: ";

for (int vertex : circuit) {

cout << vertex + 1 << " "; // Giả sử đỉnh được đánh số từ 1

}

cout << endl;

}

Tạm kết

Chu trình Euler là một khái niệm nền tảng trong lý thuyết đồ thị với nhiều ứng dụng thực tiễn. Việc hiểu rõ các định lý và thuật toán liên quan không chỉ giúp giải quyết các bài toán lý thuyết mà còn cung cấp công cụ mạnh mẽ để tối ưu hóa các quy trình trong thế giới thực. Với sự phát triển của công nghệ, việc lập trình và mô phỏng các thuật toán như Fleury trở nên dễ dàng hơn bao giờ hết, đặc biệt khi có sự hỗ trợ của các thiết bị máy tính mạnh mẽ.

Để học tập và nghiên cứu sâu hơn về các thuật toán phức tạp, bạn có thể trang bị một chiếc laptop cấu hình cao. Hãy ghé FPT Shop để tham khảo các dòng laptop gaming hoặc máy trạm di động mạnh mẽ, giúp bạn xử lý các tác vụ lập trình và mô phỏng một cách mượt mà và hiệu quả.

Xem thêm: