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.

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).

Ví dụ:

Đồ 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

Định lý Mader (1972) 
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.

Xem thêm 
k - cạnh liên thông

Chú thích

Tham khảo

Liên kết ngoài

Lý thuyết đồ thị
Họ đồ thị