1
$\begingroup$

I need to prove or disprove the following statement:

"Let $G$ be a directed acyclic graph, and $v_1v_2...v_k$ a topological sort of $G$. Then $v_kv_{k-1}...v_1$ is a valid topological sort of the transposed graph $G^T$."

(The algorithm used is the one presented in CLRS 22.4)

I think the statement is correct.

My logic is that for every two vertices $v_i,v_j$ s.t $v_i<v_j$ in the sorting of $G$, one of two conditions hold:

A) $v_j$ is a decedent of $v_i$ in $G$, so in every topological sort of $G$, $v_i$ will be before $v_j$ in the sort.

B) or there's no path from $v_i$ to $v_j$ or the contrary, so $v_i$ and $v_j$ can switch places in the sorting, depending on the order that the DFS run on $G$.

From here, if condition A held then in the sorting of $G^T$, $v_j<v_i$, because now there's a path from $v_j$ to $v_i$, and if condition B held, then the order $v_j<v_i$ is valid for some topological sort of $G^T$. And so the sorting $v_kv_{k-1}...v_1$ is valid sort of $G^T$.

Something still doesn't feel right about this... would appreciate any help or comment.

$\endgroup$
  • $\begingroup$ Are you able to edit the question to further clarify what is that something in "something still doesn't feel right about this"? I could spot a logical gap. $\endgroup$ – Apass.Jack Mar 28 at 12:31
1
$\begingroup$

A topological sort of a graph $G$ is an order $\pi$ such that if there is a directed path from $x$ to $y$ in $G$, then $x$ precedes $y$ in $\pi$.

Let us now show that $\pi^R$ is a topological sort of $G^R$. If there is a path from $x$ to $y$ in $G^R$ then there is a path from $y$ to $x$ in $G$, and so $y$ precedes $x$ in $\pi$, and so $x$ precedes $y$ in $\pi^R$.

$\endgroup$
  • $\begingroup$ Is there a difference from what you stated to statement A i presented? i don't see any.. $\endgroup$ – juleand Mar 28 at 13:42
  • $\begingroup$ My point is that you don’t need condition B at all. $\endgroup$ – Yuval Filmus Mar 28 at 13:44
  • $\begingroup$ got it, now i understand it's redundant. toda raba $\endgroup$ – juleand Mar 28 at 13:48

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.