Ho trovato diversi algoritmi che spiegano come per trovare componenti fortemente connessi in un grafico diretto, ma nessuno spiega perché si vorrebbe fare questo. Quali sono alcune applicazioni di componenti fortemente connessi?Per cosa vengono utilizzati i componenti fortemente connessi?
Dovresti dare un'occhiata al corso Introduzione ai Algoritmi di Tim Roughgarden su Coursera. Per ogni algoritmo che passa, spiega alcune applicazioni di esso. Molto utile e fa vedere il valore dello studio degli algoritmi!
L'uso di componenti fortemente connessi che ricordo che ha detto è che si potrebbe usare per trovare gruppi di persone che sono più strettamente correlati in un enorme insieme di dati. Pensa a Facebook e come consigliano le persone che potrebbero essere i tuoi amici ...
Questo potrebbe anche essere usato per vedere pezzi di una popolazione. Di ': "Wow, questo enorme componente ha l'hobby di camminare all'indietro e gli piace mangiare la pizza ammuffita!", Potrebbe mostrare una correlazione. Gli inserzionisti per la pizza ammuffita userebbero questi dati per indirizzare le persone che amano camminare all'indietro. Chissà!
Un esempio è in model checking:
Trovare componente fortemente connessa è fatto in esplicita model checking in formal verification.
nel model checking - abbiamo una macchina a stati, che rappresenta i modelli del nostro software/hardware, e cerchiamo di dimostrare temporal logic formule su di esso.
Ad esempio: La formula EG(p) mezzi: v'è un percorso nel grafico, dove per ogni stato - formula logica p rendimenti true.
Il (modello) algorithm for proving if EG(p) is true on a graph è trovare la massima componenti fortemente connesse (SCC), e poi controllando percorsi che conducono ad esso nel grafico.
Si noti che il controllo del modello viene applicato ampiamente nel settore, in particolare per dimostrare la correttezza dei componenti hardware.
(1) L'importanza della logica temporale per l'informatica è grande, e il suo inventore Amir Pnueli ha ricevuto un premio Turing per questo!
Come la maggior parte della matematica, questa è una di quelle cose che sembrano totalmente inutili finché non ne hai bisogno. – trutheality