Muestra las diferencias entre dos versiones de la página.
Ambos lados, revisión anterior Revisión previa | |||
algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos [2017/12/26 19:14] sebach ↷ Page moved from algoritmos-oia:componentes-fuertemente-conexas-en-dirigidos to algoritmos-oia:grafos-dirigidos:componentes-fuertemente-conexas-en-dirigidos |
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 ===== |