¿La ordenación topológica intenta ordenar vértices o bordes?

Question

Happy easters, everyone.

Actualmente estoy aprendiendo el tipo topológico y tengo una pregunta sobre qué tipo topológico trata realmente de ordenar.

El Algorithm Design Manual describe clasificación topológica de esta manera:

clasificación topológica es la operación más importante en los gráficos dirigidos acíclicos (DAG). Ordena los vértices en una línea de modo que todos los bordes dirigidos van de izquierda a derecha.

Esta parte audaz me confunde. ¿Lo mismo ocurre con los vértices de clasificación topológica o todos los bordes dirigidos?

Tomemos un ejemplo que también está en el libro.

Así que por lo anterior DAG, podemos conseguir una ordenación topológica (G, A, B, C, F, E, D).

Puedo entender este tipo. No sólo los vértices están ordenadas, pero los bordes también están ordenadas, es decir, G-> A-> B-> C-> F-> E-> D, esto coincide con lo anterior Descripción ADM: all directed edges go from left to right

Pero, ¿y si elimino el borde de B-> C? El gráfico resultante sigue siendo un DAG, pero ¿el tipo topológico sigue siendo (G, A, B, C, F, E, D)?

Si es Sí, entonces creo que los bordes no están ordenados, ya que A-> B-> C ya no existe, en cambio, es A-> B y A-> C. Entonces, ¿este caso sigue siendo un tipo topológico válido? ¿Todavía podemos pensar (G, A, B, C, F, E, D) es un tipo válido incluso si A es el padre de B y C?

Gracias

Answer 1

Puede considerarlo como el pedido de elementos.

deja v1, v2, ..., vn ser elementos. y deje que un borde (vi,vj) indique que vi<vj. clasificación topológica garantiza que después de la clasificación: por cada vi, y por cada vj tal que i < j, vj no es mayor que vi

O en otras anotaciones: asume (vi,vj) indican que vj depende de vi, tipo topológicos garantiza que cada el elemento "no depende" de los elementos que aparecen después de él en el género.

¿Lo mismo ocurre con los vértices de clasificación topológica o todos los bordes dirigidos?

clasificación topológica clasifica los vértices, no los bordes. Utiliza los bordes como restricciones para ordenar los vértices.

¿Pero y si elimino el borde de B-> C?

sí, cada ventaja que agrega, solo agrega una restricción.Tenga en cuenta que podría haber más de una solución factible para el tipo topológico [por ejemplo, para un gráfico sin bordes, cualquier permutación es una solución viable]. eliminar una restricción hace que toda solución anterior, que "resuelva un problema más difícil", siga siendo factible.

¿Podemos todavía piensan (G, A, B, C, F, E, D) es una especie válida incluso si A es el padre de B y C?

¡No hay ningún problema con eso! A aparece antes de B, C en el tipo topológico, por lo que no hay problema, es su padre.

Espero que sea un poco más claro.