Khác biệt giữa bản sửa đổi của “Thành phần liên thông mạnh”
n chú thích, replaced: {{cite journal → {{chú thích tạp chí |
n clean up, replaced: |thumb| → |nhỏ|, [[Image: → [[Hình:, {{reflist}} → {{Tham khảo}} using AWB |
||
| Dòng 1: | Dòng 1: | ||
[[ |
[[Hình:Scc.png|nhỏ|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]]. |
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]]. |
||
| Dòng 15: | Dòng 15: | ||
==Ghi chú== |
==Ghi chú== |
||
{{ |
{{Tham khảo}} |
||
[[Thể loại:Đồ thị]] |
[[Thể loại:Đồ thị]] |
||
Phiên bản lúc 09:57, ngày 31 tháng 12 năm 2012
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.