O tipo topológico de um gráfico original é igual ao dfs pós-ordenado de seu gráfico transposto?

Question

Tenho a intuição de que uma espécie de gráfico original

 A -> B -> C
 D -> B

topo-sort é [D, A, B, C] ou [A, D, B, C]

Se eu transpor o gráfico

  C -> B -> A   
       B -> D

o dfs pós-ordenado deste gráfico transposto também fornece [D, A, B, C] ou [A, D, B, C]

Por favor, não posso provar/refutar matematicamente.Se não for verdade, um contra-exemplo seria útil.

Uma pós-ordenação é uma lista dos vértices na ordem em que foram visitados pela última vez pelo algoritmo

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

Answer 1

Deixar $G$ seja um gráfico e $G'$ seja a versão transposta.Sua propriedade decorre dos dois fatos a seguir:

1) A ordem em que os vértices são visitados por uma visita pós-ordem em $G'$ é o inverso de uma ordem topológica $\sigma'$ para $G'$ (na verdade, essa é uma forma padrão de calcular uma ordem topológica).Você pode ver que isso é verdade observando que se $(você,v)\em G'$ então $v$ deve ser visitado antes $u$ pode ser visitado, ou seja, $v$ segue $u$ em $\sigma'$.

2) Se $\sigma'$ é uma ordem topológica para $G'$, então a ordem linear $\sigma$ obtido pela reversão $\sigma'$ é uma ordem topológica para $G$.Você pode ver que isso é verdade porque, para cada aresta $(você,v)$ de $G$, $G'$ contém $(v,você)$ e portanto $v$ precede $u$ em $\sigma'$.Isso significa que $(u,v) \in G \implica u$ precede $v$ em $\sigma$.