04 - Đồ thị liên thông

Giới thiệu

Nhắc lại khái niệm về đồ thị liên thông, là một đồ thị mà từ một đỉnh bất kỳ, ta đều có thể đi đến một đỉnh khác bất kỳ. Nếu đồ thị không liên thông, nó sẽ được chia thành các miền liên thông. Mỗi miền liên thông chính là một đồ thị con của đồ thị ban đầu và mỗi thành phần đó được gọi là thành phần liên thông. Đối với đồ thì có hướng, nếu mọi đỉnh của nó đều đến được nhau, ta nói nó là đồ thị liên thông mạnh. Nếu một đồ thị có hướng không liên thông, nhưng phiên bản vô hướng của nó là đồ thị liên thông, ta nói nó là đồ thị liên thông yếu. Đồ thị có hướng không liên thông cũng được chia thành các miền liên thông mạnh.

Bài toán quan trọng nhất liên quan đến tính liên thông của đồ thị là bài toán tìm các thành phần liên thông của đồ thị vô hướng và các thành phần liên thông mạnh của đồ thị có hướng.

Tìm các thành phần liên thông của đồ thị vô hướng

Ý tưởng cơ bản cho bài toàn tìm các thành phần liên thông của đồ thị là bắt đầu từ một đỉnh, ta tìm tất các đỉnh đến được từ nó, đưa các đỉnh này vào một thành phần liên thông, sau đó loại tất cả các đỉnh đó ra khỏi đồ thị. Lặp lại quá trình trình cho đến khi tập đỉnh của đồ thị trở thành rỗng. Việc loại bỏ này có thể thực hiện bằng cơ chế đánh dấu.

Mã giả của giải thuật có thể được mô tả như sau:

Cài đặt

Như đã phân tích trong phần duyệt DFS, rõ ràng một lần gọi DFS đơn lẻ cho một đỉnh nào đó ta không thể duyệt hết các đỉnh nếu đồ thị không liên thông. Như vậy, việc gọi DFS phải được thực hiện trong một vòng lặp và kết thúc khi không có đỉnh nào chưa duyệt.

Nhiệm vụ 1. Cho đồ thị G = (V, E) với n = |V| và m = |E|. Hãy viết chương trình liệt kê các thành phần liên thông của đồ thị.

Nhiệm vụ 2. UVA 00459 - Graph Connectivity

Tìm các thành phần liên thông mạnh trên đồ thị có hướng

Nhắc lại khái niệm về tính liên thông của đồ thị có hướng, nếu một đồ thị có hướng tự thân nó liên thông thì ta nói nó liên thông mạnh. Còn nếu bản thân nó không liên thông nhưng phiên bản vô hướng của nó liên thông thì ta nói nó liên thông yếu. Như vậy nếu một đồ thị có hướng không liên thông thì nó sẽ được chia ra thành các thành phần liên thông mạnh. Trong đó, mỗi thành phần là một đồ thị con của đồ thị ban đầu và tự thân là liên thông mạnh.

Câu hỏi đặt ra là chúng ta có thể dùng giải thuật DFS thông thường như cách tìm các thành phần liên thông trên đồ thị vô hướng để áp dụng cho việc tìm các thành phần liên thông mạnh của đồ thị có hướng được không?

Quan sát đồ thì sau đây:

Nếu gọi DFS(0) ta sẽ duyệt qua được hết các đỉnh với thứ tự: 0, 1, 2, 3, 4, 5, 7, 6. Tuy nhiên, từ 1 ta không thể đến được 0, hay từ 4 không thể đến được 3. Rõ ràng đồ thị trên được chia thành ba thành phần liên thông như sau:

Mỗi thành phần liên thông trên được gọi là một thành phần liên thông mạnh. Như vậy với thuật toán DFS thông thường, ta không thể xác định được các thành phần liên thông mạnh. Hai thuật toán phổ biến nhất cho đến nay được dùng để liệt kế các thành phần liên thông mạnh của đồ thị có hướng là của Tarjan và Kosaraju.

Để hiểu được cách hoạt động của hai thuật toán này, chúng ta cùng tìm hiểu một số đặt trưng khác của cây DFS khi ta tiến hành duyệt đồ thị. 

Duyệt đến (Explored): đỉnh bắt đầu được xem xét duyệt (có thể là được đưa vào stack) nhưng chưa duyệt xong, tức là chưa được đánh dấu là đã duyệt.

Duyệt xong (Visited): được đánh dấu là đã duyệt xong.

Cung DFS (Tree edge): cung (u, v) mà đỉnh u đã đánh dấu duyệt đến và đi đến đỉnh v khi gọi DFS, mà lúc này v chưa được duyệt đến, hay nói đơn giản là cung nối từ đỉnh cha đến đỉnh con.

Cung ngược (Back edge):  cung nối từ đỉnh v về u mà u được thăm trước v trong quá trình duyệt DFS.

Cung chéo (Cross edge): cung nối từ u qua v, trong đó u thuộc nhánh DFS này, còn v đã được duyệt trước đó thuộc nhánh DFS khác.

Cung xuôi (Forward edge): cung nối u tới v, nhưng u là tiền bối của v ở một hướng DFS khác, nên v đã được đánh dấu đã duyệt, khi backtrack về lại u, u sẽ xét tới v tiếp, nhưng vì thấy v đã được duyệt xong nên không duyệt nữa.

Nhiệm vụ 3. Viết chương trình nhập vào đồ thị có hướng giống hình minh họa trên. Thực hiện duyệt DFS từ đỉnh u rồi xuất ra từng loại cung trên đường duyệt của DFS.

Người ta chứng mình được các định lý sau về thành phần liên thông mạnh (các định lý sau đây được trích ra từ SGK chuyên Tin 1 của Hồ Sỹ Đàm, trang 171)

Định lý 5.9

Nếu x và y là hai đỉnh thuộc thành phần liên thông mạnh C thì với mọi đường đi từ x tới y cũng như từ y tới x, tất cả các đỉnh trung gian trên đường đi đều phải thuộc C.

Định lý 5.10

Với một thành phần liên thông mạnh C bất kỳ, tồn tại duy nhất một đỉnh r ∈ C sao cho mọi định của C đều thuộc nhánh DFS gốc r.

Đỉnh r mà chúng ta nói đến ở trên gọi là chốt của thành phần liên thông C. Mỗi thành phần liên thông mạnh có đúng một chốt, và nó là đỉnh nắm cao nhất trong thành phần liên thông xét về thứ tự duyệt đến trong cây DFS. Nói một cách khác, nó là tiền bối của tất cả các đỉnh thuộc C.

Định lý 5.11

Với một chốt r không là tiến bối của bất kỳ chốt nào khác thì các đỉnh thuộc nhánh DFS gốc r chính là thành phần liên thông mạnh chứa r.

Thuật toán Tarjan

Dựa trên ba định lý trên, thuật toán Tarjan sẽ đi tìm chốt r thỏa định đính lý 5.11 rồi chọn thành phần liên thông mạnh thứ nhất là nhánh DFS gốc r, loại bỏ tất cả các đỉnh này ra khỏi đồ thị. Sau đó đi tìm một chốt s khác rồi lại làm như vậy cho đến khi không cò đỉnh nào. Hay nói cách khác là thuật toán Tarjan bẻ các thành phần liên thông mạnh tại các chốt.

Như hình trên chúng ta thấy các chốt 1, 2, 5, 8 lần lượt được xác định cùng với các đỉnh trong nhánh cây DFS do nó quản lý được bẻ dần ra thành bốn thành phần liên thông.

Quá trình đó có thể được mô tả qua đoạn mã giả sau:

Void DFSVisit( u ∈ V){

       Đánh dấu u đã thăm

       For ∀ v ∈ V: (u, v) ∈ E {

              if (v chưa thăm) { DFSVisit(v)};

       }

      if (u là chốt) {

• Liệt kê thành phần liên thông mạnh tương ứng với chốt u

• Loại bỏ các đỉnh đã liệt kê ra khỏi đồ thị và cây DFS

      }

}

int main(){

Khởi tạo: Đánh dấu mọi đỉnh đều chưa thăm

for ∀ v ∈ V{

if (v chưa thăm) { DFSvisit(v);}

   }

}

Thuật toán dựa trên DFS khá tường minh, tuy nhiên, làm sao chúng ta xác định được đỉnh nào là chốt?

Để xác định được chốt chúng ta cần tìm hiểu thêm hai tính chất nữa của cây DFS: dfs_num và dfs_low

dfs_num (u): Thứ tự duyệt đến của đỉnh u trong quá trình duyệt DFS.

dfs_low(u): giá trị dfs_num nhỏ nhất của các tổ tiên mà u có thể tiếp cận được qua nhánh DFS con của nó.

Ví dụ quan sát hình sau đây:

Khi bắt đầu, chúng ta luôn khởi tạo dfs_low(u) với mọi u thuộc V là vô cực hoặc bằng chính dfs_num của nó. Khi quát trình duyệt DFS bắt đầu, từng bước một sẽ cập nhật dfs_low(u). Có một điều chúng ta cần lưu ý là với cung DFS (u,v),  việc cập nhật dfs_low(u) chỉ xảy ra khi con của nó tứ là v đã được duyệt xong. Bởi vậy khi từ u ta duyệt đến v xảy ra hai trường hợp:

Trường hợp 1: v chưa thăm, ta sẽ gọi DFS(v) để thăm v, chờ quá trình duyệt v kết thúc ta cập nhật low[u] bằng công thức:   low[u] = min( low[u], low[v]).

Trường hợp 2: v đã thăm, ta sẽ cập nhật low[u] bằng công thức: low[u] = min( low[u], num[v])

Sau khi một đỉnh duyệt xong, ta so sánh num và low của nó. Nếu low[u]  =  num[u] thì u là chốt, ta tiến hành liệt kê và xóa hết các đỉnh trong thành phần liên thông mạnh của nó ra khỏi đồ thị.

ví dụ: 

Mã giả và mô phỏng từng bước chi tiết của thuật toán các bạn tham khảo tại: baeldung.com

Nhiệm vụ 4: Thực hiện nhập vào đồ thị có hướng G, sau đó in ra các thành phần liên thông mạnh của nó theo đỉnh dạng INPUT và OUTPUT như sau:

Thuật toán Kosaraju

Được đề xuất bởi Kosaraju-Sharir vào năm 1981, thuật toán này thực hiện qua hai bước:

Bước 1. Thực hiện DFS, và đánh số lại theo thứ tự duyệt xong.

Bước 2. Đảo chiều đồ thị sau đó xét lần lượt các đỉnh theo thứ tự duyệt xong từ lớn đến nhỏ (tức là đỉnh duyệt xong sau cùng thì làm trước), với mỗi đỉnh đó ta dùng DFS hoặc BFS liệt kết các đỉnh mà nó tới được, đó chình là thành phần liên thông mạnh. Liệt kê xong thành phần liên thông nào, ta xóa luôn thành phần đó khỏi đồ thị.

Các bạn xem mô phỏng và mã giả chi tiết tại: baeldung.com

Nhiệm vụ 5. Cho đồ thị sau đây, hãy vẽ lại đồ thị và viết thứ tự duyệt xong bên cạnh nhãn của nó.

Nhiệm vụ 6. Dùng thuật toán KosaraJu để đếm số thành phần liên thông mạnh-->Link bài

Nhiệm vụ 7. Contest ngắn - Đồ thị Liên thông (cơ bản)