Khác biệt giữa bản sửa đổi của “Thành phần liên thông mạnh”
←Trang mới: “thumb|Một đồ thị với các thành phần liên thông mạnh đã được đánh dấu Một đồ thị có hướng là ''liên th…” |
(Không có sự khác biệt)
|
Phiên bản lúc 05:08, ngày 20 tháng 8 năm 2011
Một đồ 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 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[1], một biểu thức logic với các điều kiên có kích thước 2 là không thể thỏa mãn được khi và chỉ khi tồn tại một biến v sao cho v và phủ định của v nằm trong cùng một thành phần liên thông mạnh trong đồ thị quan hệ của biểu thức đó.
Ghi chú
- ^ Aspvall, Bengt; Plass, Michael F.; Tarjan, Robert E. (1979). “A linear-time algorithm for testing the truth of certain quantified boolean formulas”. Information Processing Letters. 8 (3): 121–123. doi:10.1016/0020-0190(79)90002-4.