Đường đi và chu trình Euler

Mức độ: Nâng cao

Câu đố “vẽ một nét”: vẽ hết các đường của hình mà không nhấc bút, mỗi đường vẽ đúng một lần. Trong ngôn ngữ đồ thị, đó là đường đi Euler: đường đi qua mỗi cạnh đúng một lần (đỉnh thì được đi qua nhiều lần). Nếu đường đi kết thúc ở chính đỉnh xuất phát thì gọi là chu trình Euler.

Khác với đường đi qua mỗi đỉnh đúng một lần (rất khó, phải thử gần như mọi khả năng), bài toán qua mỗi cạnh có điều kiện rất đơn giản và thuật toán chạy trong khoảng m bước.

Điều kiện để vẽ được một nét

Bậc của một đỉnh là số cạnh nối với nó. Mỗi lần đường đi đi qua một đỉnh (đến rồi đi), nó dùng hai cạnh của đỉnh đó. Vậy với các đỉnh ở giữa đường đi, các cạnh được dùng theo từng cặp: bậc phải chẵn. Chỉ đỉnh đầu và đỉnh cuối có thể dùng lẻ một cạnh.

Đồ thị vô hướng có đường đi Euler khi và chỉ khi
mọi cạnh nằm trong một thành phần liên thông	(bỏ qua các đỉnh không có cạnh nào)
số đỉnh bậc lẻ là 0	có chu trình Euler, xuất phát ở đâu cũng được
số đỉnh bậc lẻ là 2	có đường đi Euler, phải xuất phát ở một đỉnh lẻ và kết thúc ở đỉnh lẻ còn lại

Số đỉnh bậc lẻ không bao giờ là số lẻ: tổng các bậc bằng 2m (mỗi cạnh được đếm ở hai đầu), là số chẵn.

Với đồ thị có hướng, so số cạnh đi ra và số cạnh đi vào của mỗi đỉnh. Có chu trình Euler khi mọi đỉnh có vào = ra. Có đường đi Euler khi đúng một đỉnh có ra = vào + 1 (đỉnh xuất phát), đúng một đỉnh có vào = ra + 1 (đỉnh kết thúc), các đỉnh khác vào = ra. Cả hai trường hợp đều cần các cạnh nằm trong một thành phần liên thông (khi coi cạnh là vô hướng).

Thuật toán Hierholzer

Điều kiện trên cho biết có đường đi hay không. Để tìm đường đi, đi bừa theo các cạnh chưa dùng thì có thể bị kẹt sớm, bỏ sót cạnh. Hierholzer sửa lỗi đó rất gọn: dùng một ngăn xếp.

1. Đưa đỉnh xuất phát vào ngăn xếp.
2. Xem đỉnh u trên đỉnh ngăn xếp. Nếu u còn cạnh chưa dùng (u, v): đánh dấu cạnh đã dùng, đưa v vào ngăn xếp.
3. Nếu u hết cạnh: lấy u ra khỏi ngăn xếp, ghi vào kết quả.
4. Lặp lại tới khi ngăn xếp rỗng. Kết quả viết ngược lại là đường đi Euler.

Vì sao đúng: khi bị kẹt ở u (hết cạnh), u chắc chắn là điểm cuối của phần đường đi còn lại, nên ghi u vào cuối. Sau đó quay lui về đỉnh trước, nếu đỉnh đó còn cạnh thì đi tiếp một vòng mới, vòng này sẽ được “chèn” vào đường đi tại đúng đỉnh đó.

Ví dụ đồ thị có các cạnh 1-2, 2-3, 3-1, 1-4, 4-5, 5-1 (hai tam giác chung đỉnh 1), mọi đỉnh bậc chẵn. Đi từ 1, ưu tiên đỉnh kề nhỏ:

Bước	Ngăn xếp	Kết quả (theo thứ tự ghi)
đi 1 → 2 → 3 → 1	1 2 3 1
tiếp từ 1: đi 1 → 4 → 5 → 1	1 2 3 1 4 5 1
1 hết cạnh, lấy ra; 5, 4, 1 cũng hết	1 2 3	1 5 4 1
3, 2, 1 hết cạnh	(rỗng)	1 5 4 1 3 2 1

Viết ngược: 1 2 3 1 4 5 1. Vòng 1 → 4 → 5 → 1 đã được chèn vào ở lần thứ hai đi qua đỉnh 1.

Mỗi cạnh được dùng một lần, mỗi đỉnh vào và ra ngăn xếp theo số cạnh, nên số bước khoảng n + m. Mỗi đỉnh giữ một con trỏ tới cạnh kề tiếp theo cần xét, để không phải duyệt lại các cạnh đã dùng.

Python

import sys
d = sys.stdin.read().split()
n, m = int(d[0]), int(d[1])
ke = [[] for _ in range(n + 1)]
for i in range(m):
    u, v = int(d[2 + 2 * i]), int(d[3 + 2 * i])
    ke[u].append((v, i))           # lưu cả số hiệu cạnh để đánh dấu đã dùng
    ke[v].append((u, i))
le = [u for u in range(1, n + 1) if len(ke[u]) % 2 == 1]
if len(le) > 2:
    print(-1)
else:
    bat_dau = le[0] if le else next(u for u in range(1, n + 1) if ke[u])
    for u in range(1, n + 1):
        ke[u].sort()               # ưu tiên đỉnh kề nhỏ
    da_dung = [False] * m
    con_tro = [0] * (n + 1)
    ngan_xep = [bat_dau]
    ket_qua = []
    while ngan_xep:
        u = ngan_xep[-1]
        while con_tro[u] < len(ke[u]) and da_dung[ke[u][con_tro[u]][1]]:
            con_tro[u] += 1        # bỏ qua cạnh đã đi từ đầu bên kia
        if con_tro[u] < len(ke[u]):
            v, so_hieu = ke[u][con_tro[u]]
            da_dung[so_hieu] = True
            ngan_xep.append(v)
        else:
            ket_qua.append(ngan_xep.pop())
    if len(ket_qua) != m + 1:      # còn cạnh không tới được: đồ thị không liên thông
        print(-1)
    else:
        print(*ket_qua[::-1])

C++

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<pair<int, int>>> ke(n + 1);   // (đỉnh kề, số hiệu cạnh)
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back({v, i});
        ke[v].push_back({u, i});
    }
    vector<int> le;
    for (int u = 1; u <= n; u++)
        if (ke[u].size() % 2 == 1) le.push_back(u);
    if (le.size() > 2) {
        cout << -1 << "\n";
        return 0;
    }
    int batDau = 1;
    if (!le.empty()) batDau = le[0];
    else
        while (ke[batDau].empty()) batDau++;
    for (int u = 1; u <= n; u++) sort(ke[u].begin(), ke[u].end());
    vector<bool> daDung(m, false);
    vector<int> conTro(n + 1, 0), nganXep = {batDau}, ketQua;
    while (!nganXep.empty()) {
        int u = nganXep.back();
        while (conTro[u] < (int)ke[u].size() && daDung[ke[u][conTro[u]].second]) conTro[u]++;
        if (conTro[u] < (int)ke[u].size()) {
            auto [v, soHieu] = ke[u][conTro[u]];
            daDung[soHieu] = true;
            nganXep.push_back(v);
        } else {
            ketQua.push_back(u);
            nganXep.pop_back();
        }
    }
    if ((int)ketQua.size() != m + 1) {
        cout << -1 << "\n";
        return 0;
    }
    reverse(ketQua.begin(), ketQua.end());
    for (int i = 0; i <= m; i++) cout << ketQua[i] << (i < m ? ' ' : '\n');
    return 0;
}

Lưu ý: với đồ thị vô hướng, mỗi cạnh xuất hiện ở danh sách kề của cả hai đầu. Đánh dấu theo số hiệu cạnh để khi đi tới đầu bên kia không đi lại cạnh đó lần nữa. Đồ thị có hướng thì mỗi cạnh chỉ nằm ở danh sách của đỉnh đầu, không cần số hiệu.

Ưu tiên đỉnh kề nhỏ như trên cho ra đường đi nhỏ nhất theo thứ tự từ điển trong các đường đi Euler bắt đầu từ đỉnh đó, điều mà nhiều đề yêu cầu để đáp số là duy nhất.

Mô hình hóa

Cái khó của các bài Euler thường là nhận ra bài toán là Euler: phải chọn cái gì làm đỉnh, cái gì làm cạnh. Dấu hiệu: mỗi vật phải được dùng đúng một lần, và hai vật nối được với nhau khi chung một “đầu”.

Bài	Đỉnh	Cạnh
xếp các quân domino thành một hàng	các số 0 đến 6	mỗi quân domino (a, b) là cạnh a - b
nối các từ, chữ cuối của từ trước là chữ đầu của từ sau	các chữ cái	mỗi từ là cạnh có hướng từ chữ đầu tới chữ cuối
xâu ngắn nhất chứa mọi xâu nhị phân dài k	các xâu dài k - 1	mỗi xâu dài k là cạnh từ k - 1 ký tự đầu tới k - 1 ký tự cuối

Nếu bài bắt đi qua mỗi vật đúng một lần mà vật là đỉnh (ví dụ thăm mỗi thành phố một lần), đó là đường đi Hamilton, không dùng được cách này.

Luyện tập

Gồm 10 bài, chia thành 4 nhóm từ dễ đến khó. Mỗi bài có một dữ liệu kiểm tra: các bạn chạy chương trình của mình với dữ liệu đó rồi so với đáp số.

Nhóm 1. Điều kiện vẽ một nét

Bài 1. Vẽ một nét

Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u ≠ v): một đường nối hai điểm u, v của hình vẽ (hai điểm có thể được nối bằng nhiều đường). In ra YES nếu vẽ được hết các đường bằng một nét, mỗi đường vẽ đúng một lần, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
5 6 1 2 2 3 3 1 1 4 4 5 5 1	YES

Kiểm tra: nhập

6 8
1 2
2 3
3 4
4 1
1 3
2 4
4 5
5 6

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 2. Đường một chiều quay về

Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v (u ≠ v): đường một chiều từ u tới v. In ra YES nếu có cách đi qua mọi con đường đúng một lần (theo đúng chiều) rồi trở về chỗ xuất phát, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
3 4 1 2 2 1 2 3 3 2	YES

Kiểm tra: nhập

5 7
1 2
2 3
3 1
3 4
4 5
5 3
2 4

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 3. Ít nét nhất

Dữ liệu như bài 1. Mỗi nét vẽ là một đường đi không nhấc bút. In ra số nét ít nhất để vẽ hết các đường, mỗi đường vẽ đúng một lần.

Ví dụ:

Nhập	In ra
4 3 1 2 1 3 1 4	2

Kiểm tra: nhập

9 9
1 2
2 3
3 1
3 4
5 6
6 7
7 5
5 8
8 9

Xem đáp số

2

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 2. Tìm đường đi Euler

Bài 4. Nét vẽ nhỏ nhất theo thứ tự từ điển

Dữ liệu như bài 1. Nếu vẽ được bằng một nét, in ra dãy các điểm của nét vẽ (m + 1 số) nhỏ nhất theo thứ tự từ điển trong mọi cách vẽ một nét. Nếu không vẽ được, in ra -1.

Ví dụ:

Nhập	In ra
5 6 1 2 2 3 3 1 1 4 4 5 5 1	1 2 3 1 4 5 1

Kiểm tra: nhập

6 8
2 3
3 4
4 5
5 2
2 4
4 6
6 1
1 4

Xem đáp số

2 3 4 1 6 4 2 5 4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 5. Lộ trình xe buýt một chiều

Dữ liệu như bài 2 (các đường một chiều). Nếu có cách đi qua mọi con đường đúng một lần theo đúng chiều (không cần quay về chỗ cũ), in ra dãy m + 1 điểm của lộ trình nhỏ nhất theo thứ tự từ điển. Nếu không có, in ra -1.

Ví dụ:

Nhập	In ra
4 4 1 2 2 3 3 1 1 4	1 2 3 1 4

Kiểm tra: nhập

5 7
2 1
1 3
3 2
2 4
4 5
5 2
2 3

Xem đáp số

2 1 3 2 4 5 2 3

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 3. Mô hình hóa

Bài 6. Xếp domino

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có a, b (0 ≤ a, b ≤ 6): hai số trên một quân domino. Xếp mọi quân thành một hàng, được xoay từng quân, sao cho hai quân cạnh nhau có hai đầu chạm nhau mang cùng số. In ra YES nếu xếp được, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
4 1 2 2 4 3 1 4 4	YES

Kiểm tra: nhập

8
0 1
1 2
2 0
3 4
4 5
5 3
0 3
6 6

Xem đáp số

NO

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 7. Nối từ

Dòng đầu có n (1 ≤ n ≤ 10⁵), n dòng sau mỗi dòng có một từ gồm chữ cái thường (dài từ 2 đến 20 chữ). Xếp mọi từ thành một hàng sao cho chữ cái cuối của mỗi từ là chữ cái đầu của từ sau nó (không được viết ngược từ). In ra YES nếu xếp được, ngược lại in ra NO.

Ví dụ:

Nhập	In ra
3 acm malform mouse	YES

Kiểm tra: nhập

6
ban
nam
meo
ong
gac
can

Xem đáp số

YES

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 8. Xâu De Bruijn

Cho k (1 ≤ k ≤ 16). In ra xâu nhị phân ngắn nhất chứa mọi xâu nhị phân dài k làm xâu con liên tiếp. Nếu có nhiều xâu như vậy, in ra xâu nhỏ nhất theo thứ tự từ điển.

Ví dụ: nhập 2 thì in ra 00110.

Kiểm tra: nhập 4.

Xem đáp số

0000100110101111000

Hướng dẫn giải chi tiết: liên hệ tác giả.

Nhóm 4. Vận dụng

Bài 9. Người đưa thư

Dòng đầu có n, m (2 ≤ n ≤ 10⁵, 1 ≤ m ≤ 2 × 10⁵), m dòng sau mỗi dòng có u, v, w (u ≠ v, 1 ≤ w ≤ 10⁹): con đường hai chiều dài w nối u và v. Mọi điểm có đường nằm trong một thành phần liên thông, và có không quá 2 điểm bậc lẻ. Người đưa thư phải đi qua mọi con đường ít nhất một lần rồi trở về chỗ xuất phát. In ra quãng đường ngắn nhất.

Ví dụ:

Nhập	In ra
4 4 1 2 3 2 3 4 3 4 5 4 1 6	18

Kiểm tra: nhập

5 5
1 2 2
2 3 4
3 1 3
3 4 7
4 5 1

Xem đáp số

25

Hướng dẫn giải chi tiết: liên hệ tác giả.

Bài 10. Ít lộ trình một chiều nhất

Dữ liệu như bài 2 (các đường một chiều). Mỗi lộ trình là một cách đi liên tục theo đúng chiều đường. In ra số lộ trình ít nhất sao cho mỗi con đường thuộc đúng một lộ trình.

Ví dụ:

Nhập	In ra
3 3 1 2 1 3 2 3	2

Kiểm tra: nhập

7 8
1 2
1 3
1 4
5 1
6 7
7 6
2 3
4 2

Xem đáp số

4

Hướng dẫn giải chi tiết: liên hệ tác giả.

Lời giải chi tiết các bài luyện tập

Đáp số của từng bài ở ngay dưới đề để các bạn tự kiểm tra. Lời giải chi tiết (phân tích, chạy tay, chương trình Python và C++, lưu ý khi làm bài) có trong bộ tài liệu có phí của chuyên đề.

Thầy cô và các bạn muốn mua bộ tài liệu vui lòng liên hệ tác giả qua Zalo 0972465159 hoặc Facebook.