snippetMinor
Prove/disprove - reverse topological sort transpose graph
Viewed 0 times
graphreversetransposeprovetopologicaldisprovesort
Problem
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.
"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.
Solution
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$.
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$.
Context
StackExchange Computer Science Q#106167, answer score: 2
Revisions (0)
No revisions yet.