È un tipo topologico di un grafico originale come DFS post-ordinamento del suo grafico di trasposizione

Question

Ho un'intuizione che topo-sort di un grafico originale

 A -> B -> C
 D -> B

.

topo-ordinamento è [D, A, A, B, C] o [A, D, B, C]

Se mi traspondo il grafico

  C -> B -> A   
       B -> D

.

I DFS postRordering di questo grafico trasposto danno anche [D, A, B, C] o [A, D, B, C]

Per favore, non riesco a dimostrarlo / confutare matematicamente. Se non è vero, un esempio di contatore sarebbe utile.

.

Un postRordering è un elenco dei vertici nell'ordine in cui sono stati visitati l'ultima volta dall'algoritmo

https://en.wikipedia.org/wiki/depth-first_search

Answer 1

Let $ G $ Sii un grafico e $ g '$ Be è la versione trasposta. La tua proprietà segue dai seguenti due fatti:

1) L'ordine in cui i vertici sono visitati da una visita di PostRorder su $ G '$ è il contrario di un ordine topologico $ \ Sigma '$ per $ G' $ (infatti, è un modo standard per calcolare un ordine topologico). Puoi vedere che questo è vero notando che se $ (u, v) \ in g '$ allora $ V $ deve essere visitato prima di $ U $ può essere visitato, ovvero $ V $ segue < Span Class="Math-Container"> $ U $ in $ \ sigma '$ .

2) Se $ \ sigma '$ è un ordine topologico per $ g' $ , quindi L'ordine lineare $ \ sigma $ ottenuto da retromarcia $ \ sigma '$ è un ordine topologico per $ G $ . Puoi vedere che questo è vero perché, per ogni bordo $ (u, v) $ di $ G $ , $ G '$ contiene $ (v, u) $ e quindi $ V $ precedes $ U $ in $ \ Sigma '$ . Questo significa che $ (u, v) \ in g \ implica u $ precedes $ v $ in < Span Class="Math-Container"> $ \ Sigma $ .