HiveBrain v1.2.0
Get Started
← Back to all entries
snippetMinor

Prove/disprove - reverse topological sort transpose graph

Submitted by: @import:stackexchange-cs··
0
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.

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$.

Context

StackExchange Computer Science Q#106167, answer score: 2

Revisions (0)

No revisions yet.