Thành phần liên thông mạnh

Đối với các định nghĩa khác, xem Liên thông.

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ô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 trong thời gian tuyến tính. Tuy nhiên, 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 trong 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^[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ú

1. 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.