Herramientas de usuario
algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos
Diferencias
Muestra las diferencias entre dos versiones de la página.
| Ambos lados, revisión anterior Revisión previa Próxima revisión | Revisión previa | ||
|
algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos [2017/12/23 13:46] sebach |
algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos [2017/12/26 19:14] (actual) sebach ↷ Links adapted because of a move operation |
||
|---|---|---|---|
| Línea 14: | Línea 14: | ||
| Algo súper interesante, es que si tratamos a cada SCC como un nodo, y las aristas van de una SCC a otra si y sólo si hay una arista desde un nodo de la primera SCC hacia un nodo de la segunda, entonces en este nuevo grafo no hay ciclos! Si lo hubiera, significaría que las SCCs del ciclo pueden llegar de cualquiera a cualquiera, por lo que sería todo el ciclo una misma SCC. | Algo súper interesante, es que si tratamos a cada SCC como un nodo, y las aristas van de una SCC a otra si y sólo si hay una arista desde un nodo de la primera SCC hacia un nodo de la segunda, entonces en este nuevo grafo no hay ciclos! Si lo hubiera, significaría que las SCCs del ciclo pueden llegar de cualquiera a cualquiera, por lo que sería todo el ciclo una misma SCC. | ||
| - | Entonces, tenemos un [[algoritmos-oia/toposort|ordenamiento topológico]]. | + | Entonces, tenemos un [[algoritmos-oia:grafos-dirigidos:toposort|ordenamiento topológico]]. |
| ===== Aplicación ===== | ===== Aplicación ===== | ||
algoritmos-oia/grafos-dirigidos/componentes-fuertemente-conexas-en-dirigidos.1514036785.txt.gz · Última modificación: 2017/12/23 13:46 por sebach
Herramientas de la página
Excepto donde se indique lo contrario, el contenido de este wiki esta bajo la siguiente licencia: Public Domain
