Tôi đã tìm thấy một số thuật toán giải thích cách để tìm các thành phần được kết nối mạnh mẽ trong biểu đồ được chỉ dẫn, nhưng không giải thích được lý do tại sao bạn muốn thực hiện việc này. Một số ứng dụng của các thành phần được kết nối mạnh mẽ là gì?Các thành phần được kết nối mạnh được sử dụng để làm gì?
Bạn nên kiểm tra khóa học Giới thiệu về thuật toán của Tim Roughgarden trên Coursera. Đối với mọi thuật toán ông đi qua, ông giải thích một số ứng dụng của nó. Rất hữu ích, và làm cho người ta thấy giá trị của các thuật toán học tập!
Việc sử dụng các thành phần được kết nối mạnh mẽ mà tôi nhớ anh ấy nói là người ta có thể sử dụng nó để tìm các nhóm người có liên quan chặt chẽ hơn trong một tập dữ liệu khổng lồ. Hãy nghĩ về facebook và cách họ đề xuất những người có thể là bạn bè của bạn ...
Điều này cũng có thể được sử dụng để xem các phần của một tập hợp. Nói, "Wow, thành phần khổng lồ này đều có sở thích đi bộ về phía sau và thích ăn bánh pizza mốc !," nó có thể cho thấy sự tương quan. Nhà quảng cáo cho bánh pizza mốc sẽ sử dụng dữ liệu này để nhắm mục tiêu những người thích đi bộ về phía sau. Ai biết!
Một ví dụ là trong model checking:
Tìm thành phần kết nối mạnh mẽ được thực hiện trong rõ ràng model checking trong formal verification.
Trong kiểm tra mô hình - chúng tôi có một máy trạng thái đại diện cho các mô hình phần mềm/phần cứng của chúng tôi và chúng tôi cố gắng chứng minh các công thức temporal logic trên đó.
Ví dụ: Công thức EG(p) phương tiện: có một con đường trong đồ thị dưới, nơi cho mỗi tiểu bang - công thức luận lý p sản lượng true.
algorithm for proving if EG(p) is true on a graph (mô hình) là tìm các thành phần được kết nối mạnh nhất tối đa (SCC), sau đó kiểm tra các đường dẫn dẫn đến nó trong biểu đồ.
Lưu ý rằng việc kiểm tra mô hình được áp dụng rộng rãi trong ngành công nghiệp - đặc biệt là để chứng minh tính chính xác của các thành phần phần cứng.
(1) Tầm quan trọng của logic tạm thời đối với khoa học máy tính là rất tốt, và nhà phát minh của nó Amir Pnueli nhận được một giải thưởng Turing cho nó!
Giống như hầu hết các môn toán, đây là một trong những thứ trông hoàn toàn vô dụng cho đến khi bạn cần chúng. – trutheality