He encontrado varios algoritmos que explican cómo para encontrar componentes fuertemente conectados en un gráfico dirigido, pero ninguno explica por qué desea hacer esto. ¿Cuáles son algunas aplicaciones de componentes fuertemente conectados?¿Para qué se utilizan los componentes fuertemente conectados?
Debería consultar el curso Introducción a los algoritmos de Tim Roughgarden en Coursera. Para cada algoritmo que revisa, explica algunas aplicaciones de él. Muy útil, ¡y hace que uno vea el valor de estudiar algoritmos!
El uso de componentes fuertemente conectados que recuerdo que él dijo es que uno podría usarlo para encontrar grupos de personas que están más estrechamente relacionadas en un gran conjunto de datos. Piense en Facebook y en cómo recomiendan a las personas que podrían ser sus amigos ...
Esto también podría usarse para ver fragmentos de una población. Diga: "¡Wow, este enorme componente tiene la afición de caminar hacia atrás y le gusta comer pizza mohosa!", Podría mostrar una correlación. Los anunciantes de pizza enmohecida usarían esta información para dirigirse a personas que les gusta caminar hacia atrás. ¡Quién sabe!
Un ejemplo está en model checking:
Encontrar componente fuertemente conectado está hecho en model checking explícita en formal verification.
En la verificación de modelos - que tienen una máquina de estado, que representa a los modelos de nuestro software/hardware, y tratamos de demostrar temporal logic fórmulas en él.
Por ejemplo: La fórmula EG(p) medios: hay un camino en el gráfico, donde para cada estado - la fórmula lógica p rendimientos true.
El (modelo) algorithm for proving if EG(p) is true on a graph es encontrar la máxima componentes fuertemente conectados (SCC), y a continuación, comprobar caminos que conducen a que en el gráfico de.
Tenga en cuenta que la comprobación de modelos se aplica ampliamente en la industria, especialmente para probar la corrección de los componentes de hardware.
(1) La importancia de la lógica temporal de la informática es grande, y su inventor Amir Pnueli recibió un premio Turing por ello!
Como la mayoría de las matemáticas, esta es una de esas cosas que parecen totalmente inútiles hasta que las necesite. – trutheality