Bài tập: 22.5-1 CLRS
Làm cách nào để số lượng các thành phần được kết nối mạnh mẽ của biểu đồ thay đổi nếu cạnh mới?Làm cách nào để số lượng các thành phần được kết nối mạnh mẽ của biểu đồ thay đổi nếu cạnh mới được thêm
Somewhere câu trả lời được đưa ra là nếu một cạnh mới được thêm vào, một trong hai điều có thể xảy ra.
1) Nếu cạnh mới kết nối hai đỉnh thuộc về thành phần được kết nối mạnh, số lượng thành phần được kết nối mạnh sẽ vẫn như cũ.
2) Nếu, thay vào đó, cạnh kết nối hai thành phần được kết nối mạnh và mép nằm theo hướng ngược lại của đường dẫn hiện có giữa hai thành phần, sau đó sẽ tạo thành phần kết nối mạnh mới, tăng số lượng thành phần.
Tôi nghĩ điểm thứ hai là không chính xác. phép nói rằng chúng ta có hai kết nối mạnh mẽ thành phần C và C '
a) Nếu không có cạnh hoặc cạnh C-> C' tồn tại giữa họ và cạnh mới nối như C-> C' sau đó không có gì sẽ xảy ra.
b) Nếu cạnh C-> C ' tồn tại giữa chúng và cạnh mới kết nối là C' -> C thì C 'sẽ được hợp nhất thành C giảm số lượng thành phần được kết nối mạnh bởi 1 vì mọi đỉnh sẽ có thể truy cập được từ nhau.
Hãy sửa tôi nếu tôi sai.
Câu hỏi này có vẻ ngoài chủ đề bởi vì đó là về toán học –