Tìm Chu Trình, đường đi Euler

1. Lý thuyết

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 trong đó đỉnh đầu và đỉnh cuối trùng nhau (đồ thị có thể có các đỉnh cô lập). Tương tự với đường đi Euler, ngoại trừ điểm đầu và điểm cuối không trùng nhau.

Điều kiện cần để tồn tại chu trình Euler là:

• Trong đồ thị vô hướng, bậc của tất cả các đỉnh phải là số chẵn.
• Trong đồ thị có hướng, bậc ngoài và bậc trong của mỗi đỉnh phải bằng

Trong một đồ thị, nếu không tìm ra chu trình Euler, vẫn có thể tồn tại đường đi Euler. Điều kiện cần

để tồn tại đường đi Euler trong trường hợp này là:

• Trong đồ thị vô hướng, tồn tại duy nhất hai đỉnh có bậc lẻ, tất cả các đỉnh còn lại là bậc chẵn.
• Trong đồ thị có hướng, bậc ngoài và bậc trong của mỗi đỉnh bằng nhau ngoại trừ một đỉnh tại đó bậc ngoài lớn hơn bậc trong 1 đơn vị (làm đỉnh bắt đầu) và một đỉnh tại đó bậc trong lớn hơn bậc ngoài 1 đơn vị (làm đỉnh kết thúc).

2. Thuật toán Fleury

Xuất phát từ 1 đỉnh nào đó của đồ thị G(G đã loại các đỉnh cô lập) ta đi theo các cạnh của nó một cách tuỳ ý chỉ cần tuân thủ 2 quy tắc sau:

• Cạnh này không phải là “cầu” (việc bỏ cạnh này không làm cho đồ thị mất liên thông).
• Xóa bỏ cạnh đã đi qua và đồng thời xóa cả những đỉnh cô lập tạo thành.

Nếu không tìm thấy cạnh nào thỏa, thuật toán dừng. Ngược lại, từ đỉnh được nối đến, lặp lại quá trình trên. Một cách tự nhiên, chu trình Euler sẽ quay lại điểm bất đầu, đường đi Euler sẽ đến điểm kết thúc.

• Lưu ý: Khi xóa bỏ cạnh đi qua và đỉnh cô lập, sẽ hình thành một đồ thị mới. Việc xét “cầu” tiếp theo sẽ trên đồ thị mới này.
• Nhận xét: Thuật toán này tuy đơn giản nhưng thường không được sử dụng bởi việc xác định “cầu” trong đồ thị không phải đơn giản.

3. Thuật toán tìm chu trình/đường đi Euler

Từ nhận xét về thuật toán Fleury, chúng ta tìm thuật toán để thực thi một cách dễ hơn.

Cho G=(X, E) là một đồ thị gồm n đỉnh. Thuật toán tìm chu trình Euler xuất phát từ u với u là đỉnh có bậc khác 0 như sau:

‘tour’ là một stack; find_tour(u) Với mỗi cạnh e=(u,v) trong E Loại cạnh e khỏi tập E; find_tour(v); Cuối với mọi Thêm u vào stack ‘tour’; Cuối hàm

12345678

‘tour’làmộtstack;find_tour(u)Vớimỗicạnhe=(u,v)trongELoạicạnhekhỏitậpE;find_tour(v);CuốivớimọiThêmuvàostack‘tour’;Cuốihàm

Lưu ý: thuật toán này cũng có thể được sử dụng để tìm đường đi Euler bằng cách tạo một cạnh “giả” (dummy edge) nối điểm đầu và điểm cuối với nhau.

Source code (C++)

5 / 5 ( 1 vote )