Kiểm tra đồ thị 2 phía

Một trong những định nghĩa của đồ thị 2 phía:
Một đồ thị vô hướng G với tập đỉnh V và tập cạnh E gọi là đồ thị 2 phía nếu có thể chia tập đỉnh V của nó thành 2 tập con rời rạc V1 và V2, sao cho với mỗi cạnh e thuộc E: có một đỉnh thuộc V1 và đỉnh kia thuộc V2.
2000px-simple-bipartite-graph-svg                                             Đồ thị 2 phía với 2 tập đỉnh rời rạc U, V

Tính chất:
Một đồ thị là 2 phía khi và chỉ khi nó được tô bằng 2 màu.

Thuật toán:
Tô 2 màu cho đồ thị bằng BFS và DFS: với đỉnh u đang xét:
– Nếu u không kề với đỉnh nào -> tô màu bất kỳ cho u
– Xét tập đỉnh v kề u:
+ Nếu v đã được tô màu và color[v] = color[u] -> đồ thị không tô được với 2 màu
+ Nếu v chưa tô màu, ta tô màu v với màu khác với màu của u.

Code: 
Format input:
+ dòng đầu n, m tương ứng với số đỉnh, số cạnh nối.
+ m dòng tiếp theo, mỗi dòng u, v là cạnh nối đỉnh u với v
Format output: 
+ Nếu đồ thị không thể tô màu, in ra -1
+ Ngược lại in ra 2 dòng, mỗi dòng là các đỉnh thuộc cùng một màu
Dữ liệu vào đảm bảo là một đồ thị liên thông (mạnh)
Code BFS
Code DFS

Độ phức tạp: 
O(M + N)

Bình luận về đoạn code DFS trên:

bool dfs(int u, int color = 1) {
    mark[u] = color;
    cl[2 - color].pb(u);

    for(int v : adj[u]) {
        if (!mark[v] && !dfs(v, 3 - mark[u])) return 0;
        if (mark[v] == color) return 0;
    }

    return 1;
}

Lời gọi DFS này sẽ lập tức trả về kết quả ngay khi nhận biết được đồ thị đang xét không phải là một đồ thị 2 phía.
Điều này rất nguy hiểm đối với một số bài toán mà đồ thị G bao gồm nhiều đồ thị con, xem xét đoạn code kiểm tra xem G có phải là một đồ thị bao gồm các đồ thị con 2 phía không :

bool dfs(int u, int color = 1) {
mark[u] = color;
cl[2 - color].pb(u);

for(int v : adj[u]) {
if (!mark[v] && !dfs(v, 3 - mark[u])) return 0;
if (mark[v] == color) return 0;
}

return 1;
}

// in main()
for(int u = 1; u <= V; u++) {
if (mark[v]) continue;
if (!dfs(u)) return "G không phải là tập các đồ thị 2 phía";
}
return "G là tập các đồ thị 2 phía";

Lời gọi DFS(u) sẽ trả về kết quả ngay khi nó nhận biết được đồ thị con đang duyệt không phải là đồ thị 2 phía, nó không cần phải duyệt hết tất cả các đỉnh mới biết thế; vậy nên sẽ có các đỉnh u của đồ thị con chưa được duyệt qua (đánh dấu mark[u]); và rất có thể tập hợp các đỉnh này sẽ được gọi ở lệnh lặp tiếp theo và được coi như một đồ thị con mới.

Để tránh vấn đề này, code được sửa lại rất đơn giản và dễ hiểu, chỉ cần không return ngay khi biết đó là một đồ thị không phải 2 phía. Hàm DFS sửa lại như sau:

bool dfs(int u, int color = 1) {
mark[u] = color;
cl[2 - color].pb(u);

int ans = 1;
for(int v : adj[u]) {
if (!mark[v] && !dfs(v, 3 - mark[u])) ans = 0;
if (mark[v] == color) ans = 0;
}

return ans;
}

Happy coding

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s