Đồ thị liên thông

Tính liên thông (connectivity) là một trong những tính chất quan trọng nhất của đồ thị nói riêng và lý thuyết đồ thị nói chung.

Định Nghĩa

Một đồ thị được gọi là liên thông (connected) nếu có đường đi giữa mọi cặp đỉnh phân biệt của đồ thị. Ngược lại, đồ thị này được gọi là không liên thông (disconnected).

Cho đồ thị G = (X,U) vô hướng hay có hướng. Ta định nghĩa một quan hệ <=> như hệ sau trên tập đỉnh X:

Với mọi i, j thuộc X, i xấp xỉ j <=> i = j hay có dây chuyền đỉnh đầu là i và đỉnh cuối là j.

Quan hệ này có 3 tính chất: phản xạ, đối xứng và bắc cầu nên nó là một quan hệ tương đương. Do đó tập X được phân hoạch thành các lớp tương đương. Ta định nghĩa:

• Một thành phần liên thông của đồ thị là một lớp tương đương được xác định bởi quan hệ "xấp xỉ" nói trên;
• Số thành phần liên thông của đồ thị là số lượng các lớp tương đương;
• Một đồ thị liên thông là 1 đồ thị chỉ có 1 thành phần liên thông.

Thành phần liên thông

Một đồ thị không liên thông sẽ bao gồm nhiều đồ thị con liên thông, các đồ thị con này được gọi là các thành phần liên thông (connected component). Đồ thị liên thông khi và chỉ khi có một thành phần liên thông.

Trong hình trên có 4 thành phần liên thông. (Đỉnh k đứng riêng lẻ theo quy ước cũng tính là 1 thành phần liên thông)

Các định lý

• Định lý về đường đi giữa 2 đỉnh bậc lẻ: Nếu một đồ thị G (không quan tâm liên thông hay không) có đúng 2 đỉnh bậc lẻ, chắc chắn sẽ có một đường đi nối 2 đỉnh này.
• Định lý về số cạnh của đồ thị (Định lý bắt tay): Số cạnh tối đa của một đơn đồ thị không liên thông G gồm n đỉnh và k thành phần là ${\frac {(n-k)(n-k+1)}{2}}$.

Tính chất

• Đồ thị liên thông có hướng
  • Liên thông mạnh (strongly connected): Đồ thị có hướng gọi là liên thông mạnh nếu có đường đi từ a tới b và từ b tới a với mọi cặp đỉnh a và b của đồ thị. Xem thêm thành phần liên thông mạnh.
  • Liên thông yếu (weakly connected): Đồ thị có hướng gọi là liên thông yếu nếu có đường đi giữa 2 đỉnh bất kỳ của đồ thị vô hướng tương ứng với đồ thị đã cho. Tức là hủy bỏ các hướng của các cạnh trong đồ thị.
  • Liên thông một phần (unilaterally connected): Đồ thị có hướng gọi là liên thông một phần nếu với mọi cặp đỉnh a, b bất kỳ, có ít nhất một đỉnh đến được đỉnh còn lại.

• Đỉnh khớp (cut vertex/ articulation point): của một đồ thị vô hướng là đỉnh mà nếu xóa đỉnh này khỏi đồ thị và các cạnh nối đến nó thì số thành phần liên thông của đồ thị sẽ tăng thêm.
• Cạnh cầu (bridge): của một đồ thị vô hướng là cạnh mà nếu xóa đi khỏi đồ thị thì số thành phần liên thông của đồ thị sẽ tăng thêm.
• Đồ thị song liên thông (biconnectivity): là đồ thị không chứa đỉnh khớp.