Bài giảng Toán tổ hợp - Chương 4: Đại cương về đồ thị - ĐH KHTN TP.HCM

Liên thông mạnh Định nghĩa. Cho đồ thị có hướng G = (VE). Trên V ta định nghĩa quan hệ tương đương như sau: u~e ⇔ u = v hay có một đường đi từ 1 đến y và đường đi từ v đến u . a) Nếu ucv thì ta nói hai đỉnh u và v liên thông mạnh với nhau . b) Mỗi lớp tương đương được gọi là một thành phần liên thông mạnh của G. c) Nếu G chỉ có một thành phần liên thông mạnh thì G gọi là liên thông mạnh.

pdf67 trang | Chia sẻ: hoant3298 | Lượt xem: 528 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Bài giảng Toán tổ hợp - Chương 4: Đại cương về đồ thị - ĐH KHTN TP.HCM, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên

Các file đính kèm theo tài liệu này:

  • pdfslide_chuong_4_dai_cuong_ve_do_thi_793_2012607.pdf
Tài liệu liên quan