# Find all possible topological-sortings of graph G [duplicate]

A topological ordering of G is an ordering of the nodes as $$v_1,v_2,...,v_n$$ so that all edges point "forward": for every edge $$(v_i,v_j)$$, we have $$i.

Moreover, the first node in a topological ordering must be one that has no edge coming into it. Analogously, the last node must be one that has no edge leaving it.

What are the topological-sortings of the following graphs?

$$G_1$$:

Topological Sortings: (solution is from book, so it is correct)

• a b c d e
• a c b d e
• a c d b e

Okay, so if I draw the graph like a "tree" we have:

Why is a topological-sorting [a c b d e] possible if there is no path from $$c$$ to $$b$$?

$$G_2$$:

Following the same rhythm from solution to $$G_1$$, I believe the following are all possible topological sortings in $$G_2$$:

• a b c d e f
• a b d c e f
• a b d e c f
• a d b c e f
• a d b e c f
• a d e b c f
• Upvoted since you brought such nice illustrations with you, that is appreciated :) Oct 20, 2015 at 22:05
• I have a weakness in understanding concepts without visual representation, so I have to draw everything! But in the this case there is no other way unless I represent each graph as a matrix... thanks for the upvote @A. Sh! Oct 20, 2015 at 22:09

In general a topological sorting will introduce relationships that were not present in the original partial order; the only requirement is that it correctly represent every relationship that is present in the original partial order. Here $acbde$ is fine, because it preserves all of the relationships in $G_1$: it has $a$ before each of the other elements, just as $G_1$ does; it has $c$ before $d$ and $e$, just as $G_1$ does; and it has $b$ before $e$, just as $G_1$ does. $G_1$ doesn’t specify any relationship between $b$ and $c$, so the topological sort is allowed to put them in either order. (Note that you could have made exactly the same kind of objection to $acdbe$, since there’s no path from $d$ to $b$ in $G_1$.)
In any topological sort of $G_2$, $a$ must come first, and $f$ must be last. It’s also true that $b$ must come before $c$, and $d$ before $e$. There are $\binom42=6$ ways to pick two of the four spots between $a$ and $f$ to use for $b$ and $c$. Once those are picked, you can fill them with $b$ and $c$ in only one way, since $b$ has to come before $c$, and you can fill the other two with $d$ and $e$ in only one way. Thus, there are $6$ possible topological sorts, and you’ve correctly found all of them.