Khác biệt giữa bản sửa đổi của “Thành phần liên thông mạnh”

n
không có tóm lược sửa đổi
n (Robot: Sửa đổi hướng)
nKhông có tóm lược sửa đổi
Một [[đồ thị (lý thuyết đồ thị)#đồ thị có hướng|đồ thị có hướng]] là ''liên thông mạnh'' nếu như có đường từ bất kì đỉnh nào tới bất kì đỉnh nào khác. Một '''thành phần liên thông mạnh''' của một đồ thị có hướng là một đồ thị con tối đại liên thông mạnh. Nếu mỗi thành phần liên thông mạnh được co lại thành một đỉnh, thì đồ thị sẽ trở thành một [[đồ thị có hướng không có chu trình]].
 
[[Thuật toán Kosaraju]], [[thuật toán tìm thành phần liên thông mạnh của Tarjan|thuật toán Tarjan]], và [[thuật toán Gabow]] đều có thể tìm các thành phần liên thông mạnh của một đồ thị cho trước mộttrong cáchthời hiệugian quảtuyến tính. Tuy nhiên trong thực tế, các thuật toán của Tarjan và Gabow thường được sử dụng nhiều hơn do chúng chỉ cần thực hiện [[tìm kiếm theo chiều sâu]] một lần thaytrong khi thuật toán của Kosaraju cần hai lần.
 
Thuật toán tìm thành phần liên thông mạnh có thể được dùng để giải [[bài toán thỏa mãn biểu thức logic]] trong đó mỗi điều kiện có hai biến số. Theo Aspvall, Plass, và Tarjan đã chứng minh năm 1979<ref>{{chú thích tạp chí
494

lần sửa đổi