Khác biệt giữa bản sửa đổi của “Thành phần liên thông mạnh”
Nội dung được xóa Nội dung được thêm vào
n r2.7.1) (Bot: Thêm uk:Компонента сильної зв'язності графа |
n chú thích, replaced: {{cite journal → {{chú thích tạp chí |
||
Dòng 5:
[[Thuật toán Kosaraju]], [[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ột cách hiệu quả. Tuy nhiên trong thực tế, các thuật toán của Tarjan và Gabow thường được sử dụng do chúng chỉ cần thực hiện [[tìm kiếm theo chiều sâu]] một lần thay vì 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>{{
| last1 = Aspvall | first1 = Bengt
| last2 = Plass | first2 = Michael F.
| |||