Khác biệt giữa bản sửa đổi của “Thành phần liên thông mạnh”
n clean up, replaced: |thumb| → |nhỏ|, [[Image: → [[Hình:, {{reflist}} → {{Tham khảo}} using AWB |
n Bot: Di chuyển 12 liên kết ngôn ngữ đến Wikidata tại d:q2003238 Addbot |
||
| Dòng 18: | Dòng 18: | ||
[[Thể loại:Đồ thị]] |
[[Thể loại:Đồ thị]] |
||
[[ar:مخطط قوي التوصيل]] |
|||
[[ca:Component fortament connex]] |
|||
[[cs:Silně souvislá komponenta]] |
|||
[[en:Strongly connected component]] |
|||
[[es:Componente fuertemente conexo]] |
|||
[[fr:Composante fortement connexe]] |
|||
[[it:Componente fortemente connessa]] |
|||
[[pl:Składowa silnie spójna]] |
|||
[[ru:Компонента сильной связности в орграфе]] |
|||
[[th:ส่วนประกอบที่เชื่อมกันแบบเข้ม]] |
|||
[[uk:Компонента сильної зв'язності графа]] |
|||
[[zh:强连通分量]] |
|||
Phiên bản lúc 16:00, ngày 13 tháng 3 năm 2013
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.