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.