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

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

Xem thêm

sửa

Chú thích

sửa
  1. ^ a b c Graph Theory, Reinhard Diestel, Springer-Verlag, New York 1997, 2000

Tham khảo

sửa

Liên kết ngoài

sửa