Chu trình đồ thị tiếng anh là gì năm 2024

Question

Trong bài viết này, chúng ta sẽ cùng nhau đi sâu hơn vào cách xác định chu trình trên đồ thị và những bài toán ứng dụng của nó.

Nội dung chính Show

1. Phát biểu bài toán
2. Ý tưởng
Phân loại các cung trên cây DFS
Phân tích giải thuật
3. Cài đặt
II. Ví dụ minh họa
1. Bài toán 1
Đề bài

Giải thuật DFS\text{DFS} là một công cụ rất hữu hiệu để xác định chu trình trên đồ thị. Sau đây, chúng ta sẽ cùng tìm hiểu về ý tưởng của giải thuật.

1. Phát biểu bài toán

Cho một đơn đồ thị vô hướng GG gồm nn đỉnh và mm cung (có thể có "khuyên" - cạnh tự nối một đỉnh với chính nó). Các đỉnh của đồ thị được đánh số từ 11 tới nn.

Một chu trình trên đồ thị là một đường đi (x1,x2,…,xk,x1)(x_1, x_2, \dots, x_k, x_1) với hai đỉnh đầu và cuối của đường đi giống nhau.

Hãy xác định đồ thị trên có chứa chu trình nào hay không?

Input:

Dòng đầu tiên chứa hai số nguyên nn và mm - số đỉnh và số cạnh của đồ thị (1≤n,m≤105)(1 \le n, m \le 10^5).
mm dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u,vu, v - thể hiện một cạnh của đồ thị nối hai đỉnh uu và vv.

Output:

In ra YES
3 nếu đồ thị có chứa chu trình, ngược lại in ra
YES 4.

Sample Input 1:

Sample Output 1:

YES

Sample Input 2:

Sample Output 2:

NO

2. Ý tưởng

Phân loại các cung trên cây DFS

Trong quá trình duyệt DFS\text{DFS} trên đồ thị, nếu như ta chỉ giữ lại các cạnh (u,v)(u, v) với uu là cha của v,v, rồi định hướng cạnh đó theo chiều (u→v),(u \rightarrow v), thì ta sẽ thu được một đồ thị mới dạng cây, gọi là cây DFS\text{DFS}. Các cạnh được giữ lại sẽ gọi là cạnh thuộc cây DFS,\text{DFS}, còn các cạnh không được giữ lại gọi là cạnh không thuộc cây DFS\text{DFS}.

Chu trình đồ thị tiếng anh là gì năm 2024

Cây DFS của một đồ thị gồm 9 đỉnh, các cạnh màu trắng là cạnh được giữ lại

Giả sử đồ thị đang xét là đồ thị có hướng, xét mọi cung được thăm và không được thăm trong quá trình DFS,\text{DFS}, ta có các loại cung sau:

Cung của cây DFS (Tree Edges): Các cung được thăm trong quá trình DFS\text{DFS} (cung màu trắng nét liền).
Cung xuôi (Forward edges): Cung không thuộc cây DFS\text{DFS} có dạng (u→v)(u \rightarrow v); trong đó uu là cha của vv trong quá trình DFS\text{DFS} (cạnh xanh lá).
Cung ngược (Back edges): Cung không thuộc cây DFS\text{DFS} và có dạng (v→u)(v \rightarrow u); trong đó uu là cha của vv (cạnh đỏ) nhưng vv đã được thăm trước đó do một dây chuyền DFS\text{DFS} khác.
Cung chéo (Cross edges): Cung không thuộc cây DFS\text{DFS}, trong đó uu và vv thuộc hai nhánh khác nhau của cùng một cây DFS\text{DFS} (cạnh tím).

Còn nếu như xét trên đồ thị vô hướng, thì chỉ tồn tại duy nhất hai loại cung là cung thuộc cây DFS và cung ngược (không thuộc cây DFS).

Phân tích giải thuật

Từ định nghĩa về cây DFS\text{DFS} ở trên, ta nhận thấy rằng:

Một cây DFS\text{DFS} của đồ thị sẽ chứa toàn bộ các đỉnh thuộc cùng một thành phần liên thông của đồ thị, nhưng không phải tất cả các cạnh.
Cây DFS\text{DFS} của đồ thị là một đồ thị không có chu trình.
Nếu như trong quá trình duyệt DFS,\text{DFS}, xuất hiện một cung ngược, thì chắc chắn thành phần liên thông hiện tại có chứa chu trình (bời vì sẽ có một đường đi quay lại được đỉnh đã thăm ở phía trên).

Nhận xét trên cho ta ý tưởng về cách xác định một đồ thị có chu trình hay không vô cùng đơn giản như sau:

Sử dụng DFS, duyệt từng thành phần liên thông của đồ thị. Nếu trong quá trình duyệt phát hiện một cung ngược, thì chắc chắn đồ thị có chứa chu trình.

Việc xác định một cung có phải cung ngược hay không rất dễ, bằng cách sử dụng một mảng visited[u]\text{visited}[u] để đánh dấu lại đỉnh uu đã duyệt qua hay chưa. Sau đó, nếu như trong quá trình duyệt nhánh textDFStext{DFS} gốc uu mà có một cạnh (u,v)(u, v) mà vv đã thăm rồi, thì cung (u→v)(u \rightarrow v) sẽ là cung ngược.

Giải thuật có thể thực hiện tương tự nhau ở cả đồ thị vô hướng lẫn có hướng.

3. Cài đặt

Ngôn ngữ C++:


# include 

# define int long long

# define task "detect_cycle."
using namespace std;
const int maxn = 1e5 + 10;
typedef int arr[maxn];
vector < int > adj[maxn];
// Nhập dữ liệu đồ thị.
void enter(int &n, int &m, vector < int > adj[])
{
    cin >> n >> m;
    for (int u = 1; u <= n; ++u)
        adj[u].clear();
    for (int i = 1; i <= m; ++i)
    {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
}
// DFS để tìm chu trình từ một cây DFS gốc u.
bool dfs_find_cycle(int u, int par, vector < int > adj[], arr visited)
{
    visited[u] = true;
    for (int v: adj[u])
    {
        // Nếu đỉnh v chưa thăm thì đi thăm v và xem nhánh DFS từ v
        // có tạo ra chu trình hay không.
        if (!visited[v])
        {
            if (dfs_find_cycle(v, u, adj, visited))
                return true;
        }
        // Nếu v đã thăm và v không phải đỉnh vừa gọi đệ quy ở bước
        // trước, thì cung (u, v) là một cung ngược -> có chu trình.
        else if (v != par)
            return true;
    }
    return false;
}
// Xác định có tồn tại chu trình trên đồ thị hay không.
void solution(int n, vector < int > adj[], arr visited)
{
    fill(visited + 1, visited + n + 1, 0);
    // Thử DFS từ các đỉnh và dựng cây DFS.
    for (int u = 1; u <= n; ++u)
        if (!visited[u])
        {
            if (dfs_find_cycle(u, -1, adj, visited))
            {
                cout << "YES" << endl;
                return;
            }
        }
    cout << "NO" << endl;
}
main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    arr visited;
    enter(n, m, adj);
    solution(n, adj, visited);
    return 0;
}

II. Ví dụ minh họa

1. Bài toán 1

Đề bài

Cho một dãy số AA gồm nn phần tử a0,a1,…,an−1a_0, a_1, \dots, a_{n - 1}. Xuất phát từ một phần tử ở vị trí ii bất kỳ, ta sẽ di chuyển trên mảng theo trình tự sau:

Nếu ai<0,a_i < 0, di chuyển tới phần tử (i−ai) mod n(i - a_i) \text{ mod } n.
Nếu ai>0,a_i > 0, di chuyển tới phần tử (i+ai) mod n(i + a_i) \text{ mod } n.

Nếu như giá trị ai mod n=0,a_i \text{ mod } n = 0, thì sẽ không có sự di chuyển nào diễn ra cả.

Hãy xác định xem quá trình di chuyển trên có thể tạo thành một chu trình di chuyển trên dãy số hay không? Lưu ý rằng, nếu như bước di chuyển tự đi tới chính nó thì không tính là một chu trình.

là ai Hỏi Đáp Là gì Học Tốt Tiếng anh

Chu trình đồ thị tiếng anh là gì năm 2024

1. Phát biểu bài toán

2. Ý tưởng

Phân loại các cung trên cây DFS

Phân tích giải thuật

3. Cài đặt

II. Ví dụ minh họa

1. Bài toán 1

Đề bài

Bài Viết Liên Quan

Quảng Cáo

Có thể bạn quan tâm

Toplist được quan tâm

Quảng cáo

Xem Nhiều

Quảng cáo

Chúng tôi

Điều khoản

Trợ giúp

Mạng xã hội