Considere el DAG con Considere V = {1, 2, 3, 4, 5, 6}, que se muestra a continuación. ¿Cuál de los siguientes NO es un ordenamiento topológico?
(A) 1 2 3 4 5 6
(B) 1 3 2 4 5 6
(C) 1 3 2 4 6 5
(D) 3 2 4 1 6 5
Respuesta: (D)
Explicación: En la opción D, 1 aparece después 2 y 3 que no es posible en la clasificación topológica .
En el DAG dado, es directamente visible que hay un borde saliente desde el vértice 1 al vértice 2 y 3, por lo tanto, 2 y 3 no pueden estar antes del vértice 1, por lo que claramente la opción D es una clasificación topológica incorrecta.
Pero para las preguntas en las que no es directamente visible, deberíamos saber cómo encontrar una especie de DAG topológico.
Esta solución es aportada por Parul Sharma.
Cuestionario de esta pregunta
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