K-liên thông
Đồ thị G được gọi là k - liên thông (tiếng Anh: k-connected) hay đầy đủ hơn là k - đỉnh liên thông (tiếng Anh: k-vertex-connected) nếu ta xóa đi không quá k-1 đỉnh bất kì và các cạnh liên thuộc với các đỉnh đó thì đồ thị còn lại vẫn liên thông[1].
Nhận xét:
- Mọi đồ thị (không rỗng) đều là 0 - liên thông.
- Mọi đồ thị liên thông đều là 1 - liên thông.
- Đồ thị đầy đủ là (n-1) - liên thông.
- Một đồ thị là k - liên thông thì cũng là h - liên thông với h<k, 0<k.
Số k lớn nhất sao cho G là k - liên thông được gọi là độ liên thông (tiếng Anh: connectivity), ký hiệu là κ(G)[1].
Ví dụ:
-
Khi xóa 3 đỉnh bất kì của H và các cạnh liên thuộc với chúng, đồ thị còn lại vẫn liên thông.
-
Nếu ta xóa đi 4 đỉnh màu đỏ thì đồ thị còn lại không liên thông nữa.
- Đồ thị H trong hình vẽ có 6 đỉnh, nếu ta xóa đi 3 đỉnh bất kì và các cạnh liên thuộc với chúng, đồ thị còn lại vẫn liên thông, do đó H là 3 - liên thông, và tất nhiên cũng là 2 - liên thông và 1 - liên thông. Nếu như ta xóa 4 đỉnh màu đỏ thì đồ thị không còn liên thông nữa, do đó κ(H) = 4.
Định lý về đồ thị k - liên thông
sửaĐịnh lý Mader (1972)
sửa- Mọi đồ thị có bậc trung bình (tiếng Anh: avergae degree) lớn hơn hoặc bằng 4k thì có ít nhất một đồ thị con là k - liên thông[1].