L'ordinamento topologico tenta di ordinare i vertici oi bordi?

Question

Happy easters, tutti.

Attualmente sto imparando l'ordinamento topologico e ho una domanda su quale tipo di topologia cerca di ordinare realmente.

Il Algorithm Design Manual descrive ordinamento topologico in questo modo:

ordinamento topologico è l'operazione più importante grafo aciclico diretto (DAG). Ordina i vertici su una linea in modo che tutti i bordi diretti vadano da sinistra a destra.

Questa parte audace mi confonde. Quindi l'ordinamento topologico ordina i vertici o tutti i bordi diretti?

Facciamo un esempio che è anche nel libro.

Così, per quanto sopra DAG, si può ottenere un ordinamento topologico (G, A, B, C, F, E, D).

Posso capire questo tipo. Non solo i vertici sono ordinati, ma i bordi sono anche ordinati, cioè, G-> A-> B-> C> F-> E-> D, questo corrisponde a quanto sopra descrizione ADM libro: all directed edges go from left to right

Ma cosa succede se rimuovo il bordo di B-> C? Il grafico risultante è ancora un DAG, ma l'ordinamento topologico è ancora (G, A, B, C, F, E, D)?

Se è Sì, penso che i bordi non siano ordinati, poiché A-> B-> C non esiste più, invece, A-> B e A-> C. Quindi, questo caso è ancora un tipo topologico valido? Possiamo ancora pensare (G, A, B, C, F, E, D) è un ordinamento valido anche se A è il genitore di B e C?

Grazie

Answer 1

Si può pensare a come ordinare gli elementi.

lasciare v1, v2, ..., vn essere elementi. e lasciare un margine (vi,vj) denotare che vi<vj. ordinamento topologico garantisce che dopo l'ordinamento: per ogni vi, e per ogni vj tale che i < j, vj non è maggiore di vi

In altre notazioni: assumere (vi,vj) indicano che vj è dipendente vi, tipi topologici garantisce che ciascun l'elemento "non dipende" da alcun elemento che appare dopo di esso nell'ordinamento.

Così l'ordinamento topologico ordina i vertici o tutti i bordi diretti?

ordinamento topologico ordina i vertici, non i bordi. Usa i bordi come vincoli per ordinare i vertici.

Ma cosa succede se rimuovo il bordo di B-> C?

sì, ogni spigolo aggiunto, basta aggiungere un vincolo.Si noti che potrebbe esserci più di una soluzione fattibile per il tipo topologico [ad esempio, per un grafico senza spigoli, qualsiasi permutazione è una soluzione fattibile]. rimuovendo un vincolo, rende possibile qualsiasi soluzione precedente, che "risolve un problema più difficile".

Possiamo ancora pensare (G, A, B, C, F, E, D) è una specie valida anche se A è il genitore di B e C?

Non c'è nessun problema! A appare prima di B, C nel tipo topologico, quindi non c'è problema è il loro padre.

Spero che sia un po 'più chiaro.