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 đủ $K_{n}$ 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ụ:

• 
  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

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