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
Đị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[1].
Xem thêm
- k - cạnh liên thông
Chú thích
- ^ a b c Graph Theory, Reinhard Diestel, Springer-Verlag, New York 1997, 2000
Tham khảo
Liên kết ngoài
Bài viết này vẫn còn sơ khai. Bạn có thể giúp Wikipedia mở rộng nội dung để bài được hoàn chỉnh hơn.
|