0
$\begingroup$

I have an intuition that topo-sort of an original graph

 A -> B -> C
 D -> B

topo-sort is [D, A, B, C] or [A, D, B, C]

If I transpose the graph

  C -> B -> A   
       B -> D

the postordering dfs of this transposed graph also gives [D, A, B, C] or [A, D, B, C]

Please, I can't mathematically prove/disprove it. If not true, an counter example would helpful.

A postordering is a list of the vertices in the order that they were last visited by the algorithm

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

$\endgroup$
9
  • $\begingroup$ Try your claim on your transposed graph, and see if it still makes sense. $\endgroup$ – Yuval Filmus Apr 25 '20 at 9:08
  • $\begingroup$ Hi @Yuval Filmus. I showed an example of the transposed graph in the question. I have tried several others, my claim seems to be correct based on my limited cases I tried. I can't find an counter example, and I am not capable of prove it mathematically $\endgroup$ – wenchao jiang Apr 25 '20 at 9:14
  • $\begingroup$ I was suggesting to try your claim not on the graph you give, but on its transposition. $\endgroup$ – Yuval Filmus Apr 25 '20 at 9:15
  • $\begingroup$ I try as you suggested. The claim still hold, the topo and dfs order are [C B A D, C B D A]. Do I miss anything? $\endgroup$ – wenchao jiang Apr 25 '20 at 9:25
  • 1
    $\begingroup$ Please update your question to explain what you're doing. We cannot guess your mind. It's even better if you explain what you mean by "post-order DFS", since I've never heard this term. $\endgroup$ – Yuval Filmus Apr 25 '20 at 9:33
0
$\begingroup$

Let $G$ be a graph and $G'$ be it's transposed version. Your property follows from the following two facts:

1) The order in which vertices are visited by a postorder visit on $G'$ is the reverse of a topological order $\sigma'$ for $G'$ (in fact, that's a standard way to compute a topological order). You can see that this is true by noticing that if $(u,v) \in G'$ then $v$ must be visited before $u$ can be visited, i.e., $v$ follows $u$ in $\sigma'$.

2) If $\sigma'$ is a topological order for $G'$, then the linear order $\sigma$ obtained by reversing $\sigma'$ is a topological order for $G$. You can see that this is true because, for every edge $(u,v)$ of $G$, $G'$ contains $(v,u)$ and therefore $v$ precedes $u$ in $\sigma'$. This means that $(u,v) \in G \implies u$ precedes $v$ in $\sigma$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.