Dado un gráfico con aristas dirigidas y no dirigidas. Se da que las aristas dirigidas no forman ciclo. ¿Cómo asignar direcciones a los bordes no dirigidos para que el gráfico (con todos los bordes dirigidos) permanezca acíclico incluso después de la asignación?
Por ejemplo, en el siguiente gráfico, los bordes azules no tienen direcciones.
Recomendamos encarecidamente minimizar su navegador y probarlo usted mismo primero. La idea es utilizar Clasificación topológica . Los siguientes son dos pasos utilizados en el algoritmo. 1) Considere el subgrafo solo con bordes dirigidos y encuentre la ordenación topológica del subgrafo. En el ejemplo anterior, la clasificación topológica es {0, 5, 1, 2, 3, 4}.
El siguiente diagrama muestra la clasificación topológica para el gráfico de ejemplo anterior.
2) Use la clasificación topológica anterior para asignar direcciones a bordes no dirigidos. Para cada borde no dirigido (u, v), asígnele la dirección de u a v si u viene antes que v en la clasificación topológica; de lo contrario, asígnele la dirección de v a u.
El siguiente diagrama muestra direcciones asignadas en el gráfico de ejemplo.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA