Đồ thị song liên thông

Đôi khi có ích để thiết kế nhiều hơn một đường đi giữa các điểm trên một đồ thị, nhằm dự phòng khả năng không liên lạc được với các đỉnh. Ví dụ, ta có thể chạy từ quận 1 đến công viên Lê Thị Riêng ngay như nếu đường Cách Mạng Tháng 8 bị kẹt xe bằng cách đi qua đường 3 tháng 2 rồi Sư Vạn Hạnh. Các đường dây chính của một mạch điện thường là song liên, như vậy phần còn lại của mạch điện vẫn có thể làm việc nếu một thành phần của mạch bị hỏng. Một ứng dụng khác (không thực tế lắm nhưng là một minh họa tự nhiên cho khái niệm này) là trong tình trạng chiến tranh, ta làm sao để địch phải dội bom ít nhất hai nơi mới cắt được đường tiếp vận.

Nút bản lề trong một đồ thị liên thông là nút mà nếu xóa nó, sẽ tách đồ thị này thành hai thành phần. Đồ thị không có nút bản lề được gọi là song liên thông. Trong đồ thị song liên, mỗi cặp điểm có ít nhất hai đường dẫn nối chúng với nhau. Đồ thị mà không song liên sẽ được chia thành các thành phần song liên.

Vậy thì làm thế nào để xác định các nút bản lề của một đồ thị liên thông cho trước? Cách dễ thấy nhất là theo định nghĩa mà làm, tức là xét từng nút, kiểm tra xem nó có phải bản lề bằng cách ngắt nó ra khỏi đồ thị, duyệt đồ thị mới bằng DFS hoặc BFS để kiếm tra. Tuy nhiên, cách này khá thô thiển. Có một cách khác hiệu quả hơn nhiều: mở rộng DFS.

Bạn đọc thông thạo về phép duyệt theo chiều sâu DFS sẽ thấy rằng, trong quá trình duyệt sẽ hình thành một cây, gọi là cây DFS. Cấu trúc của cây này phụ thuộc vào thứ tự duyệt các đỉnh trong input. Dễ thấy một nút x trên cây nếu có đường nối đến nút khác thì nút khác ấy phải nằm trên đường đi từ nút gốc đến nút x.

Một đỉnh x không phải là nút bản lề nếu mỗi nút con y đều có một nút thấp hơn hoặc bằng được nối với nút cao hơn trên cây, từ đó cho một liên kết khác từ x đến y. Sự kiểm chứng này không đúng cho nút gốc của cây DFS, vì không có nút nào cao hơn nút gốc. Nút gốc là một nút bản lề nếu nó có hai con trở lên, bởi vì đường dẫn nối các con của nút gốc phải đi xuyên qua nút gốc. Ta dễ dàng đưa những sự kiểm tra này vào DFS bằng cách thay đổi thủ tục node-visit thành một hàm có chức năng trả lại nút cao nhất trên cây (có giá trị val thấp nhất) trong quá trình tìm kiếm.

Hãy ngẫm thật kĩ đoạn cài đặt sau đây và bạn sẽ thấy thế nào là nghệ thuật cài đặt của Robert Sedgewick:

function visit(k: integer): integer;
var t: link; m, min: integer;
begin
    id := id + 1; val[k] := id; min := id; t := adj[k];
    while t <> z do
    begin
        if val[t^.v] = 0 then
        begin
            m := visit(t^.v);
            if m < min then min := m;
            if m >= val[k] then write(name(k));
        end
        else if val[t^.v] < min then min := val[t^.v];
        t := t^.next;
    end;
    visit := min;
end;

Một cách đệ quy, thủ tục này từ các nút con của đỉnh k đi dọc theo các đường nối lên trên cao để xác định nút cao nhất có thể với đến trên cây, và dùng thông tin trên để xác định k có là nút bản lề hay không. Thông thường, sự tính toán này chỉ đơn giản là phép kiểm tra nút con (có giá trị val nhỏ nhất) có là cao hơn nút k trên cây hay không.

Tuy nhiên, ta cần có một phép kiểm tra thêm để xác định k có là gốc của cây DFS (nói cách khác là xem xét đây có phải là lần gọi visit đầu tiên cho thành phần liên thông chứa k hay không), bởi vì ta đang dùng cùng một chương trình đệ quy cho cả 2 trường hợp. Phép kiểm tra này được thực hiện ngoài visit và vì vậy trong đoạn mã trên không có nó.

Các thành phần song liên của một đồ thị được tìm ra trong một thời gian tuyến tính. Mặc dù trình này chỉ đơn giản là in ra các nút bản lề của một đồ thị, nó dễ dàng được mở rộng, như ta đã làm cho các thành phần liên thông, để làm các xử lý thêm trên các nút bản lề và các thành phần song liên. Bởi vì đây là một thủ tục DFS, thời gian thực hiện là tỉ lệ với V+E (nếu dựa trên ma trận kề, thì sẽ là O(N^2) bước).

Trong các loại ứng dụng nêu trên, tính song liên được dùng để tăng độ tin cậy, có ích để phân rã các đồ thị lớn thành các phần quản lý được. Rõ ràng trong nhiều ứng dụng, các thành phần liên thông được xử lý từng cái một, nhưng thỉnh thoảng cũng cần xử lý từng thành phần song liên.

Theo “Cẩm Nang Thuật Toán” Tập 2, nhà xuất bản Khoa Học Kỹ Thuật – 1994

Advertisements

4 thoughts on “Đồ thị song liên thông

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