Euler và Chu trình Euler: Khám phá đồ thị

I. Tổng quan

    Những lý thuyết cơ bản của lý thuyết đồ thị chỉ mới được đề xuất từ thế kỷ XVIII, bắt đầu từ một bài báo của Leonhard Euler về bài toán 77 cây cầu ở Königsberg - một bài toán cực kỳ nổi tiếng:

    Thành phố Königsberg thuộc Đức (nay là Kaliningrad thuộc CHLB Nga) được chia làm 44 vùng bằng các nhánh của con sông Pregel giống như hình vẽ bên dưới. Vào năm 1736,1736, người ta đã xây 77 cây cầu nối các vùng này với nhau. Người dân ở đây tự hỏi, liệu có cách nào xuất phát tại một địa điểm trong thành phố (11 trong 44 vùng), đi qua 77 chiếc cầu, mỗi chiếc đúng một lần rồi lại quay trở về điểm xuất phát hay không?

    

    Euler đã giải quyết thành công bài toán này bằng cách mô tả bản đồ khu vực bởi một đa đồ thị, với các khu vực là các đỉnh và những chiếc cầu là các cạnh nối. Bài toán nói trên có thể được tổng quát hóa thành bài toán: Có tồn tại chu trình trong đa đồ thị, đi qua tất cả các cạnh và mỗi cạnh đúng một lần hay không?

    Bởi vì Leonhard Euler là người đã giải bài toán này, nên dạng chu trình đi qua tất cả các cạnh, mỗi cạnh đúng một lần được gọi là chu trình Euler, như một cách để tri ân nhà bác học vĩ đại của lịch sử loài người.

II. Các khái niệm và định lý

    Có 44 khái niệm mà chúng ta cần nắm vững trước khi đi vào tìm hiểu về giải thuật tìm chu trình Euler:

  • Chu trình đơn chứa tất cả các cạnh của đồ thị được gọi là chu trình Euler.
  • Đường đi đơn chứa tất cả các cạnh của đồ thị được gọi là đường đi Euler.
  • Một đồ thị có chu trình Euler được gọi là đồ thị Euler.
  • Một đồ thị có đường đi Euler được gọi là đồ thị nửa Euler.

    

    Trong các đồ thị trên, đồ thị G1G_1 có chu trình Euler là (a,e,c,d,e,b,a);(a, e, c, d, e, b, a); đồ thị G2G_2 không có chu trình Euler nhưng có đường đi Euler là (a,c,d,e,b,a,d,b),(a, c, d, e, b, a, d, b), nên nó là đồ thị nửa Euler; còn đồ thị G3G_3 không có chu trình Euler lẫn đường đi Euler.

    Ngoài ra, có một số định lý quan trọng sẽ hỗ trợ cho quá trình phát triển thuật toán tìm chu trình Euler:

Định lý 1

    Một đồ thị vô hướng liên thông G=(V,E)G=(V,E) có chu trình Euler khi và chỉ khi mọi đỉnh của nó đều có bậc chẵn: deg(v)0 (mod 2);vVdeg⁡(v)≡0 \ (\text{mod } 2); ∀v∈V.

    Chứng minh: Nếu GG có chu trình Euler, thì khi đi dọc theo chu trình đó, mỗi khi đi qua một đỉnh thì bậc của đỉnh đó tăng thêm 22 (có hai cạnh liên thuộc ở hai đầu). Mà chu trình Euler lại đi qua tất cả các cạnh, nên suy ra mọi đỉnh của đồ thị đều có bậc chẵn. Từ đó cũng suy ra điều ngược lại: Nếu GG liên thông và các đỉnh đều có bậc chẵn, thì ta sẽ xây dựng được thuật toán tìm chu trình Euler trên đồ thị.

Hệ quả 1

    Một đồ thị vô hướng liên thông G=(V,E)G = (V, E) có đường đi Euler khi và chỉ khi nó có đúng 22 đỉnh bậc lẻ.

    Chứng minh: Nếu GG có đường đi Euler thì chỉ có đỉnh bắt đầu và đỉnh kết thúc đường đi có bậc lẻ, còn mọi đỉnh khác trên đường đi đều có bậc chẵn. Ngược lại, nếu đồ thị liên thông có đúng 22 đỉnh bậc lẻ thì ta sẽ thêm vào một cạnh giả nối hai đỉnh bậc lẻ đó, rồi tìm chu trình Euler. Sau khi tìm xong, loại bỏ cạnh giả đi là thu được đường đi Euler.

Định lý 2

    Một đồ thị có hướng liên thông yếu G=(V,E)G = (V, E) có chu trình Euler thì mọi đỉnh của nó có bán bậc ra bằng bán bậc vào: deg+(v)=deg(v),vVdeg^{+}(v) = deg^{-}(v), \forall v \in V. Ngược lại, nếu GG liên thông yếu và mọi đỉnh của nó có bán bậc ra bằng bán bậc vào, thì GG có chu trình Euler (đồng nghĩa với việc GG là đồ thị liên thông mạnh).

    Chứng minh: Tương tự cách chứng minh định lý 11.

Hệ quả 2

    Một đồ thị có hướng liên thông yếu G=(V,E)G = (V, E) có đường đi Euler nhưng không có chu trình Euler nếu và chỉ nếu tồn tại đúng hai đỉnh s,tVs, t \in V sao cho:

    deg+(s)deg(s)=eg+(t)deg(t)=1deg^{+}(s) - deg^{-}(s) = eg^{+}(t) - deg^{-}(t) = 1

    còn tất cả các đỉnh còn lại của đồ thị đều có bán bậc ra bằng bán bậc vào.

    Việc chứng minh định lý số 11 sẽ giúp chúng ta xây dựng được một thuật toán hữu ích để tìm chu trình Euler trên đồ thị Euler, đó là giải thuật Fleury.

III. Giải thuật Fleury tìm chu trình Euler

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

    Cho đa đồ thị vô hướng liên thông GG gồm nn đỉnh, mm cạnh. Hãy tìm ra một chu trình Euler của đồ thị?

    Input:

  • Dòng đầu tiên chứa số nguyên dương nn - số đỉnh của đồ thị (1n100)(1 \le n \le 100).
  • Các dòng tiếp theo, mỗi dòng chứa ba số nguyên u,v,ku, v, k - cho biết giữa hai đỉnh uu và vv có kk cạnh nối.

    Output:

  • Ghi ra một chu trình Euler tìm được. Nếu đồ thị ban đầu không phải đồ thị Euler, in ra 00.

    Sample Input:

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

    Sample Output:

1 2 3 1 3 4 1

2. Giải thuật cơ sở

Ý tưởng

    Trước hết, ta sẽ một số khái niệm như sau để thống nhất thuật toán trên cả đồ thị vô hướng và có hướng:

  • Nếu nói cạnh (u,v)(u,v) thì hiểu là cạnh nối hai đỉnh uuvv trên đồ thị vô hướng, hiểu là cung nối từ đỉnh uu tới đỉnh vv trên đồ thị có hướng.
  • Gọi cạnh (u,v)(u,v) là cạnh “một đi không trở lại” nếu như từ uu ta đi tới vv theo cạnh đó, sau đó xóa cạnh này đi thì không còn cách nào từ vv quay trở lại uu cả.

    Như vậy, giải thuật Fleury đơn giản nhất có thể phát biểu như sau:

    Xuất phát từ một đỉnh, ta đi tùy ý theo các cạnh, tuân theo hai nguyên tắc:

  • Một là xóa bỏ cạnh vừa đi qua.
  • Hai là chỉ chọn đi vào cạnh "một đi không trở lại" nếu như không còn cạnh nào khác để chọn. Việc kiểm tra một cạnh (u,v)(u, v) có phải là cạnh "một đi không trở lại" hay không có thể thực hiện bằng cách: Thử xóa cạnh đó đi rồi dùng BFSBFS để tìm đường đi từ vv tới u,u, nếu không tìm được thì cạnh đó chắc chắn là cạnh "một đi không trở lại".

    Ta sẽ cài đặt giải thuật bằng cách sử dụng một ma trận kề adj[u][v]\text{adj}[u][v] để biểu diễn đồ thị cho thuận tiện khi thực hiện thao tác xóa cạnh, ngoài ra có thêm một hàm kiểm tra xem đồ thị có phải là đồ thị Euler hay không.

Cài đặt

    Ngôn ngữ C++:

#include <bits/stdc++.h>
#define task "Euler."

using namespace std;

typedef int arr[1001];
typedef int arr2[1001][1001];

// Nhập dữ liệu cho đồ thị. Thao tác này có thể dễ dàng điều chỉnh 
// khi đề bài thay đổi cách nhập liệu.
void enter(int &n, arr2 adj, arr deg)
{
    cin >> n;

    int u, v, k;
    while (cin >> u >> v >> k)
    {
        adj[u][v] = adj[v][u] = k;

        deg[u] += k;
        deg[v] += k;
    }
}

void dfs(int n, int u, int cnt_comps, arr2 adj, arr number) // Đếm số TPLT của đồ thị.
{
    number[u] = cnt_comps;

    for (int v = 1; v <= n; ++v)
        if (!number[v] && adj[u][v])
            dfs(n, v, cnt_comps, adj, number);
}

// Kiểm tra đồ thị có phải đồ thị Euler không.
bool check_euler_graph(int n, arr2 adj, arr deg)
{
    // Đếm số thành phần liên thông của đồ thị.
    int cnt_comps = 0;
    arr number;
    for (int u = 1; u <= n; ++u)
        if (!number[u])
        {
            ++cnt_comps;
            dfs(n, u, cnt_comps, adj, number);
        }

    // Nếu đồ thị không liên thông thì nó không phải đồ thị Euler.
    if (cnt_comps > 1)
        return false;

    // Nếu tồn tại đỉnh có bậc lẻ thì cũng không phải đồ thị Euler.
    for (int u = 1; u <= n; ++u)
        if (deg[u] % 2 == 1)
            return false;

    return true;
}

// Kiểm tra xem nếu xóa cạnh (u, v) thì có thể đi ngược từ v về u không.
bool can_go_back(int n, arr2 adj, int u, int v)
{
    // Thử xóa cạnh (u, v), tức là số cạnh nối giảm đi 1.
    --adj[u][v];
    --adj[v][u];

    // Sau khi xóa cạnh (u, v), thử bfs từ v tới u xem có đi được nữa không.
    bool is_free[n + 1];
    fill(is_free + 1, is_free + n + 1, true);

    queue < int > path;
    path.push(v);

    while (!path.empty())
    {
        int cur = path.front();
        path.pop();

        if (cur == u)
            break;

        for (int next_v = 1; next_v <= n; ++next_v)
            if (is_free[next_v] && adj[cur][next_v])
            {
                is_free[next_v] = false;
                path.push(next_v);
            }
    }

    // Nối lại cạnh (u, v) do lúc nãy đã thử xóa cạnh này đi.
    ++adj[u][v];
    ++adj[v][u];

    return !is_free[u];
}

// Giải thuật Fleury tìm chu trình Euler trên đồ thị.
void fleury(int n, arr2 adj, arr deg)
{
    // Đồ thị không phải đồ thị Euler -> In ra 0.
    if (!check_euler_graph(n, adj, deg))
    {
        cout << 0;
        return;
    }

    int cur_vertex = 1, next_v = 0;
    vector < int > circuit;
    step.push_back(cur_vertex);

    do
    {
        next_v = 0;

        // Lần lượt chọn các cạnh liên thuộc với đỉnh hiện tại
        // trong chu trình đang xét.
        for (int v = 1; v <= n; ++v)
            if (adj[cur_vertex][v])
            {
                next_v = v;

                // Ưu tiên chọn cạnh không phải là cạnh "một đi không trở lại".
                if (can_go_back(n, adj, cur_vertex, next_v))
                    break;
            }

        // Tìm được 1 cạnh nối chưa bị xóa có thể đi được.
        if (next_v != 0)
        {
            // Xóa cạnh nối đó đi.
            --adj[cur_vertex][next_v];
            --adj[next_v][cur_vertex];

            step.push_back(next_v); // Đưa đỉnh này vào danh sách các đỉnh trên chu trình.

            cur_vertex = next_v;
        }
    }
    while (next_v != 0);

    // In ra chu trình tìm được.
    for (int u: circuit)
        cout << u << ' ';
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    arr2 adj;
    arr deg;

    enter(n, adj, deg);
    fleury(n, adj, deg);

    return 0;
}

3. Cải tiến với ngăn xếp

    Trong trường hợp đồ thị có số cạnh vừa phải, có thể cải tiến bằng giải thuật như sau: Bắt đầu từ một chu trình đơn CC bất kỳ, chu trình này tìm được bằng cách xuất phát từ một đỉnh bất kỳ, đi tùy ý theo các cạnh cho tới khi quay trở về đỉnh xuất phát (lưu ý đi qua cạnh nào xóa luôn cạnh đó). Khi đó, có thể xảy ra hai trường hợp:

  • Nếu chu trình CC này chứa tất cả các cạnh của đồ thị thì đó là một chu trình Euler.
  • Nếu không, ta xét các đỉnh uu thuộc chu trình C,C, nếu còn một cạnh liên thuộc nào đó của uu chưa bị xóa thì ta lại tiếp tục đi từ u,u, theo các cạnh tùy ý tới khi quay trở về uu để thu được một chu trình đơn khác qua uu.
  • Cuối cùng loại bỏ uu khỏi chu trình CC và chèn chu trình mới tìm được vào đúng vị trí của uu vừa xóa, ta sẽ thu được một chu trình CC’ mới lớn hơn chu trình CC ban đầu. Cứ làm như vậy cho tới khi tìm được chu trình Euler.

    Để cài đặt việc xóa và thêm đỉnh một cách hiệu quả, ta sẽ sử dụng một ngăn xếp vertexes\text{vertexes} để kiểm soát các đỉnh uu trên chu trình. Mọi cài đặt khác vẫn giống như giải thuật cơ bản, chỉ riêng hàm xác để xác định một cạnh (u,v)(u, v) có phải cạnh "một đi không trở lại" hay không sẽ không cần thiết nữa.

    Một lưu ý nho nhỏ là đối với ngôn ngữ lập trình C++, nếu như số cạnh trên đồ thị quá dày, thì quá trình DFS\text{DFS} sẽ phải gọi đệ quy rất sâu, dẫn đến tràn ngăn xếp của bộ nhớ (ngăn xếp lưu các lời gọi đệ quy). Để giải quyết vấn đề này, các bạn cần mở tăng dung lượng mặc định của ngăn xếp trong C++, xem hướng dẫn đối với các IDE dưới đây:

Cài đặt

    Ngôn ngữ C++:

#include <bits/stdc++.h>
#define task "Euler."

using namespace std;

typedef int arr[1001];
typedef int arr2[1001][1001];

// Nhập dữ liệu cho đồ thị. Thao tác này có thể dễ dàng điều chỉnh 
// khi đề bài thay đổi cách nhập liệu.
void enter(int &n, arr2 adj, arr deg)
{
    cin >> n;

    int u, v, k;
    while (cin >> u >> v >> k)
    {
        adj[u][v] = adj[v][u] = k;

        deg[u] += k;
        deg[v] += k;
    }
}

void dfs(int n, int u, int cnt_comps, arr2 adj, arr number) // Đếm số TPLT của đồ thị.
{
    number[u] = cnt_comps;

    for (int v = 1; v <= n; ++v)
        if (!number[v] && adj[u][v])
            dfs(n, v, cnt_comps, adj, number);
}

// Kiểm tra đồ thị có phải đồ thị Euler không.
bool check_euler_graph(int n, arr2 adj, arr deg)
{
    // Đếm số thành phần liên thông của đồ thị.
    int cnt_comps = 0;
    arr number;
    for (int u = 1; u <= n; ++u)
        if (!number[u])
        {
            ++cnt_comps;
            dfs(n, u, cnt_comps, adj, number);
        }

    // Nếu đồ thị không liên thông thì nó không phải đồ thị Euler.
    if (cnt_comps > 1)
        return false;

    // Nếu tồn tại đỉnh có bậc lẻ thì cũng không phải đồ thị Euler.
    for (int u = 1; u <= n; ++u)
        if (deg[u] % 2 == 1)
            return false;

    return true;
}

// Giải thuật Fleury tìm chu trình Euler trên đồ thị, cải tiến với stack.
void fleury_stack(int n, arr2 adj, arr deg)
{
    // Đồ thị không phải đồ thị Euler -> In ra 0.
    if (!check_euler_graph(n, adj, deg))
    {
        cout << 0;
        return;
    }

    stack < int > vertexes;
    vector < int > circuit;
    vertexes.push(1);

    while (!vertexes.empty())
    {
        int u = vertexes.top();

        for (int v = 1; v <= n; ++v)
            if (adj[u][v]) // Nếu có cạnh (u, v)
            {
                // Xóa cạnh khỏi đồ thị.
                --adj[u][v];
                --adj[v][u];

                // Đẩy tiếp v vào ngăn xếp.
                vertexes.push(v);
                break;
            }

        // Nếu đỉnh ở đầu ngăn xếp vẫn là u, suy ra vòng lặp trên không tìm được 
        // đỉnh nào kề với u, vậy nó là một đỉnh thuộc chu trình.
        if (u == vertexes.top())
        {
            circuit.push_back(u);
            vertexes.pop();
        }
    }

    // In ra chu trình tìm được, nhưng theo thứ tự ngược lại vì các đỉnh.
    // đẩy vào stack bị ngược so với các cung định hướng. Đối với đồ thị
    // vô hướng thì điều này không quan trọng, nhưng nếu là đồ thị có hướng
    // thì bắt buộc phải làm như vậy, nếu không chu trình sẽ sai so với các
    // cung của đồ thị ban đầu.
    for (int i = circuit.size() - 1; i >= 0; --i)
        cout << circuit[i] << ' ';
}

main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    int n;
    arr2 adj;
    arr deg;

    enter(n, adj, deg);
    fleury_stack(n, adj, deg);

    return 0;
}

IV. Tài liệu tham khảo

Nguồn: Viblo

Bình luận
Vui lòng đăng nhập để bình luận
Một số bài viết liên quan