Me gustaría dividir un gráfico dirigido en subgráficos que contengan un ciclo simple (si hay una solución para el gráfico dado).
Sé que hay algoritmos para calcular los componentes fuertemente conectados de un gráfico dirigido, como el algoritmo de Kosaraju, por ejemplo. Estoy buscando algo similar, pero un componente fuertemente conectado no necesariamente contiene un ciclo simple.
¿Puede alguien señalarme el algoritmo que estoy buscando?
Comencemos observando que si algún conjunto de vértices induce un ciclo simple, entonces estos vértices están en el mismo componente fuertemente conectado (SCC), por lo que cualquier ciclo simple de un grafo dirigido debe residir completamente en un SCC. También tenga en cuenta que dos vértices que están conectados por aristas en ambas direcciones es un ciclo simple, por lo que los únicos SCC que no contienen un ciclo simple son singletons (es decir, consisten en exactamente 1 vértice). El vértice contenido en tal SCC no es parte de ningún ciclo simple (de lo contrario, estaría en un SCC diferente según nuestra primera observación), por lo que cualquier gráfico con SCC singleton no admite una partición del tipo que está buscando.
De ello se deduce que dicha partición se puede obtener (si existe) dividiendo el gráfico en SCC.
vvg