Do czego są używane silnie połączone komponenty?

Question

Znalazłem kilka algorytmów, które wyjaśniają, jak , jak znaleźć silnie połączone komponenty na grafice, ale żadne nie wyjaśniają, dlaczego chciałbyś to zrobić. Jakie są aplikacje silnie połączonych komponentów?

Answer 1

Powinieneś sprawdzić kurs Wprowadzenie do algorytmów Tima Roughgardena na Courserze. Dla każdego algorytmu, który podał, wyjaśnia niektóre jego zastosowania. Bardzo przydatne i sprawia, że ​​można dostrzec wartość nauki algorytmów!

Używanie silnie połączonych komponentów, o których pamiętam, mówi, że można go użyć do znalezienia grup osób, które są bardziej powiązane w olbrzymim zbiorze danych. Pomyśl o Facebooku i o tym, jak polecają osoby, które mogą być Twoimi przyjaciółmi ...

Można to również wykorzystać do obejrzenia fragmentów populacji. Powiedz: "Wow, ten wielki komponent ma hobby chodzenia do tyłu i lubi jeść spleśniałą pizzę!", Może pokazać korelację. Reklamodawcy używający spleśniałej pizzy wykorzystają te dane do kierowania na osoby, które lubią chodzić do tyłu. Kto wie!

Answer 2

Jednym z przykładów jest w model checking:

Znalezienie mocno połączony komponentu odbywa się w wyraźnej model checking w formal verification.

W modelu kontroli - mamy maszynę do stanu, który reprezentuje model naszego oprogramowania/sprzętu, a my staramy się udowodnić temporal logic formuły na nim.

na przykład: Wzór EG(p) sposobem: jest ścieżka na wykresie, gdzie dla każdego stanu - skład logicznego p plonów true.

Model algorithm for proving if EG(p) is true on a graph (model) to znajdowanie maksymalnych silnie połączonych komponentów (SCC), a następnie sprawdzanie ścieżek prowadzących do niego na wykresie.

Należy zauważyć, że sprawdzenie modelu jest szeroko stosowane w branży - szczególnie w celu udowodnienia poprawności komponentów sprzętowych.

---

(1) Znaczenie logiki temporalnej do informatyki jest wielki, a jej wynalazca Amir Pnueli otrzymał nagrodę Turinga za to!