Tính liên thông của đồ thị¶
Tính liên thông trên đồ thị vô hướng¶
Định nghĩa 31 (Đồ thị liên thông)
Một đồ thị vô hướng được gọi là liên thông (hay connected, hay связанный) nếu giữa hai đỉnh bất kì của đồ thị tồn tại đường đi.
Đồ thị chỉ gồm một đỉnh duy nhất cũng được coi là đồ thị liên thông.
Hình 11 Đồ thị liên thông¶
Định nghĩa 32 (Thành phần liên thông)
Cho đồ thị \(G = (V, E)\). Nếu đồ thị con \(G' = (V', E')\) của \(G\) là đồ thị liên thông thì \(G'\) được gọi là thành phần liên thông (hay connected component, связанный компонент) của đồ thị \(G\).
Hình 12 Các thành phần liên thông trên đồ thị¶
Trên hình 12 có ba thành phần liên thông:
thành phần liên thông thứ nhất gồm hai đỉnh \(v_1\), \(v_2\), và cạnh \(e_{12}\)
thành phần liên thông thứ hai gồm ba đỉnh \(v_3\), \(v_4\), \(v_6\), và các cạnh \(e_{36}\), \(e_{46}\)
thành phần liên thông thứ ba chỉ gồm đỉnh \(v_5\).
Đôi khi việc bỏ đi một đỉnh và tất cả cạnh liên thuộc với nó sẽ tăng số lượng thành phần liên thông hơn so với đồ thị ban đầu. Các đỉnh như vậy gọi là đỉnh cắt (hay cut vertices), hoặc nút khớp (hay articulation nodes).
Tương tự, khi bỏ đi một cạnh mà số lượng thành phần liên thông tăng lên thì cạnh đó gọi là cạnh cắt (hay cut edges) hoặc cầu (hay bridge).
Ở hình 13 là một đồ thị liên thông, nếu chúng ta xóa cạnh \(e_{24}\) (cạnh màu đỏ) thì chúng ta sẽ có hai thành phần liên thông:
thành phần liên thông thứ nhất gồm hai đỉnh \(v_1\) và \(v_2\)
thành phần liên thông thứ hai gồm bốn đỉnh \(v_3\), \(v_4\), \(v_5\) và \(v_6\).
Hình 13 Ví dụ về cầu¶
Đồ thị có thể có nhiều cầu. Ở hình 13, thay vì xóa cạnh \(e_{24}\), nếu ta xóa cạnh \(e_{46}\) thì cũng làm tăng số thành phần liên thông. Do đó cạnh \(e_{46}\) cũng là cầu. Tương tự cho cạnh \(e_{12}\), ...
Tính liên thông trên đồ thị có hướng¶
Một đồ thị có hướng được gọi là:
liên thông mạnh (hay strongly connected) nếu tồn tại đường đi giữa hai đỉnh bất kì của đồ thị;
liên thông yếu (hay weakly connected) nếu phiên bản vô hướng của nó là đồ thị liên thông.
Bài toán xác định các thành phần liên thông¶
Bài toán xác định các thành phần liên thông của đồ thị là một bài toán quan trọng trong lý thuyết đồ thị. Bài toán sẽ tìm tất cả thành phần liên thông của đồ thị vô hướng.
Để liệt kê các thành phần liên thông của đồ thị vô hướng \(G = (V, E)\) ta thực hiện các bước sau:
Bắt đầu từ một đỉnh bất kì, ta tìm tất cả đỉnh đến được từ đỉnh đó. Như vậy chúng ta tìm được một thành phần liên thông.
Loại những đỉnh ở thành phần liên thông đầu tiên và xét một trong những đỉnh còn lại. Lặp lại công việc ở bước 1, ta tìm tất cả đỉnh đến được từ đỉnh đang xét. Như vậy chúng ta tìm được thêm một thành phần liên thông.
Thực hiện đến khi đã xét hết tất cả đỉnh trong đồ thị.
Ở đây, để tìm tất cả đỉnh đến được từ một đỉnh nào đó trong đồ thị ta sử dụng thuật toán DFS (Depth First Search, Duyệt Sâu) hoặc BFS (Breadth First Search, Duyệt Rộng).