Định chiều đồ thị

1. Bài toán định chiều đồ thị

– Cho đồ thị vô hướng, liên thông, thay mỗi cạnh bằng một cung định hướng để được một đồ thị có hướng, liên thông mạnh.

– Bài toán tổng quát: Với đồ thị vô hướng G = (V, E), hãy tìm cách thay mỗi cạnh của đồ thị bằng một cung định hướng để được đồ thị mới có ít thành phần liên thông mạnh nhất.

– Ứng dụng: Trong 1 hệ thống đường phố, có thể quy định các con đường là đường 1 chiều mà vẫn đảm bảo sự đi lại giữa 2 nút giao thông bất kì không ?

2. Các tính chất

– Đồ thị vô hướng, liên thông định chiều được chỉ khi:
+ Mỗi cạnh thuộc ít nhất một chu trình đơn
+ Suy ra mỗi cạnh đều không phải là cầu (bridge)

– Nếu đồ thị liên thông, mỗi cạnh thuộc ít nhất 1 chu trình đơn, thì thuật toán định chiều DFS (dưới đây) sẽ cho 1 đồ thị liên thông mạnh. Nếu không thì sẽ cho đồ thị định hướng ít thành phần liên thông mạnh nhất, cầu của đồ thị sẽ được định hướng thành cung nối giữa 2 thành phần liên thông mạnh.

3. Thuật toán và mã giả

– Thuật toán: định chiều đồ thị bằng DFS, trong quá trình duyệt DFS đỉnh u, xét các đỉnh v kề với nó:
+ Nếu v chưa thăm, định chiều cạnh u-v thành u->v và thăm v
+ Nếu v đã thăm, định chiều cạnh u-v thành u->v

– Mã giả:

void dfs(int u) {
    visit[u] = true;
    for(int v kề u) ) {
        Định chiều u-v thành u->v
        if (!visit[v]) dfs(v);
    }
}

// in main()
for(int u : Vertices)
    if (!visit[u]) dfs(u)

Trong lập trình, việc định chiều cạnh u-v thành cạnh u->v có thể được hiểu là loại đi chiều v->u

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