Hamilton Graphs and Hamiltonian Cycles

I. Tổng quan

    Khái niệm về đường đi và chu trình Hamilton được đưa ra bởi William Rowan Hamilton vào năm 1856,1856, sau khi ông thiết một trò chơi trên khối đa diện 2020 đỉnh, 3030 cạnh, 1212 mặt, mỗi cạnh là một ngũ giác đều và người chơi cần chọn các cạnh để thành lập một đường đi qua 55 đỉnh cho trước (còn gọi là trò chơi Icosian).

    

    Bài toán tổng quát được Hamilton đưa ra là: Tìm một chu trình đơn đi qua tất cả các đỉnh trên đồ thị, mỗi đỉnh đúng một lần sau đó quay trở về điểm xuất phát. Cho đến nay, bài toán này vẫn chưa có lời giải đối với trường hợp đồ thị tổng quát. Những bài toán liên quan tới chu trình Hamilton đều là những bài toán NP - hard. Mọi thuật toán tìm kiếm chu trình Hamilton hiện nay đều chỉ thiết kế dựa trên mô hình duyệt mà thôi.

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

    Cho đồ thị G=(V,E)G = (V, E) có nn đỉnh. Vẫn tương tự như đồ thị Euler, chúng ta sẽ có một số khái niệm đối với đồ thị Hamilton:

  • Một chu trình x1,x2,,xn,x1x_1,x_2,…,x_n,x_1 được gọi là chu trình Hamilton nếu xixj;i,j:1i<jnx_i≠x_j; ∀i,j:1≤i<j≤n.
  • Đường đi x1,x2,,xnx_1,x_2,…,x_n được gọi là đường đi Hamilton nếu xixj;i,j:1i<jnx_i≠x_j; ∀i,j:1≤i<j≤n.
  • Đồ thị có chu trình Hamilton được gọi là đồ thị Hamilton.
  • Đồ thị có đường đi Hamilton được gọi là đồ thị nửa Hamilton. Lưu ý, chu trình Hamilton không phải là đường đi Hamilton (do đỉnh xuất phát được thăm tới 22 lần), khác với chu trình Euler cũng chính là đường đi Euler. Ngoài ra, quy ước rằng đồ thị chỉ gồm 11 đỉnh là đồ thị Hamilton, nhưng đồ thị gồm 22 đỉnh liên thông sẽ không phải đồ thị Hamilton.

    Các bạn có thể xem một số hình vẽ đồ thị dưới đây để hiểu hơn về các khái niệm:

    

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

    Những định lý dưới đây cho chúng ta một vài dấu hiệu nhận biết một đồ thị có phải đồ thị Hamilton hay không:

Định lý 1

    Xét với đồ thị vô hướng G,G, trong đó tồn tại kk đỉnh sao cho nếu xóa đi kk đỉnh này cùng với những cạnh liên thuộc của chúng thì đồ thị nhận được sẽ có nhiều hơn kk thành phần liên thông. Khi đó, khẳng định GG không phải là đồ thị Hamilton.

Định lý 2 (Định lý Dirak, 1952)

    Xét đơn đồ thị vô hướng G=(V,E)G = (V, E) có nn đỉnh (n3)(n \ge 3). Nếu mọi đỉnh đều có bậc không nhỏ hơn n2\left\lfloor{\frac{n}{2}}\right\rfloor thì GG là đồ thị Hamilton.

Định lý 3 (Định lý Ghouila - Houiri, 1960)

    Xét đơn đồ thị có hướng liên thông mạnh G=(V,E)G = (V, E) có nn đỉnh. Nếu trên phiên bản vô hướng của G,G, mọi đỉnh đều có bậc không nhỏ hơn nn thì GG là đồ thị Hamilton.

Định lý 4 (Định lý Ore, 1960)

    Xét đơn đồ thị vô hướng G=(V,E)G = (V, E) có nn đỉnh (n3)(n \ge 3). Xét mọi cặp đỉnh không kề nhau, nếu không có cặp đỉnh nào có tổng bậc nhỏ hơn nn thì GG là đồ thị Hamilton.

Định lý 5 (Định lý Meynie, 1973)

    Xét đơn đồ thị có hướng liên thông mạnh G=(V,E)G = (V, E) có nn đỉnh. Nếu trên phiên bản vô hướng của G,G, mọi cặp đỉnh không kề nhau đều có tổng bậc không nhỏ hơn 2n12n - 1 thì GG là đồ thị Hamilton.

Định lý 6 (Định lý Bondy - Chvátal, 1972)

    Xét đồ thị vô hướng G=(V,E)G = (V, E) có nn đỉnh, với mỗi cặp đỉnh không kề nhau (u,v)(u, v) mà deg(u)+deg(v)n,deg(u) + deg(v) \ge n, ta thêm một cạnh nối uu và vv. Cứ làm như vậy tới khi không thêm được cạnh nào nữa, thì ta thu được một bao đóng của đồ thị G,G, kí hiệu cl(G)cl(G). Khi đó, GG là đồ thị Hamilton nếu và chỉ nếu cl(G)cl(G) là đồ thị Hamilton.

III. Thuật toán tìm chu trình Hamilton

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

    Cho đồ thị vô hướng liên thông GG có nn đỉnh và mm cạnh. Hãy tìm ra các chu trình Hamilton xuất phát từ đỉnh 11 của đồ thị?

    Input:

  • Dòng đầu tiên chứa hai số nguyên dương nn và mm - số đỉnh và số cạnh của đồ thị (1n100,1m100)(1 \le n \le 100, 1 \le m \le 100).
  • mm dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, v - thể hiện một cạnh nối giữa hai đỉnh uu và vv của đồ thị.

    Output:

  • Ghi ra các chu trình Hamilton xuất phát từ đỉnh 11 của đồ thị, mỗi chu trình trên một dòng.

    Sample Input

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

    Sample Output:

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

2. Thiết kế giải thuật

    Đến nay, vẫn chưa có thuật toán nào tốt hơn quay lui để tìm ra các chu trình Hamilton trên một đồ thị tổng quát. Cài đặt dưới đây sẽ tìm ra tất cả các chu trình Hamilton xuất phát từ đỉnh 11 của đồ thị, các chu trình khác có thể thu được bằng cách hoán vị vòng quanh.

Cài đặt

    Ngôn ngữ C++:

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

using namespace std;

const int maxn = 101;

typedef int arr[maxn];
typedef int arr2[maxn][maxn];

// Nhập dữ liệu.
void enter(int &n, int &m, arr2 adj, arr deg)
{
    cin >> n >> m;

    memset(adj, 0, sizeof(adj));
    memset(deg, 0, sizeof(deg));

    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;

        ++adj[u][v];
        ++adj[v][u];

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

// Kiểm tra điều kiện đồ thị Hamilton.
bool check_hamilton_graph(int n, arr deg)
{
    for (int u = 1; u <= n; ++u)
        if (deg[u] < 2)
            return false;

    return true;
}

// In một chu trình Hamilton.
void print_hamilton_circuit(int n, arr circuit)
{
    for (int i = 1; i <= n; ++i)
        cout << circuit[i] << ' ';
    cout << circuit[1] << endl;
}

// Quay lui tìm các chu trình Hamilton.
void find_hamilton_circuit(int i, int n, arr2 adj, arr circuit, arr is_free)
{
    // Thử chọn các đỉnh v kề với đỉnh liền trước trong chu trình và chưa thăm.
    for (int v = 1; v <= n; ++v)
        if (is_free[v] && adj[circuit[i - 1]][v])
        {
            // Ghi nhận đỉnh v vào chu trình.
            circuit[i] = v;

            // Nếu chưa chọn đủ n đỉnh thì tiếp tục chọn.
            if (i < n)
            {
                // Đánh dấu đỉnh v đã chọn.
                is_free[v] = false;

                // Gọi đệ quy thử chọn đỉnh tiếp theo.
                find_hamilton_circuit(i + 1, n, adj, circuit, is_free);

                // Loại bỏ đỉnh v khỏi chu trình để thử trường hợp khác.
                is_free[v] = true;
            }
            // Đã chọn đủ n đỉnh và đỉnh thứ n tới được đỉnh 1 
            // Kết luận đã tìm được chu trình Hamilton.
            else if (adj[v][circuit[1]])
                print_hamilton_circuit(n, circuit);
        }
}

// Xử lý các trường hợp.
void solution(int n, arr2 adj, arr deg, arr is_free, arr circuit)
{
    fill(is_free + 1, is_free + n + 1, 1);
    circuit[1] = 1;

    if (!check_hamilton_graph(n, deg))
        cout << 0;
    else
        find_hamilton_circuit(2, n, adj, circuit, is_free);
}

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

    int n, m;
    arr2 adj;
    arr deg, is_free, circuit;

    enter(n, m, adj, deg);
    solution(n, adj, deg, is_free, circuit);

    return 0;
}

III. 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