Find all possible topological-sortings of graph G

Question

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

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

Answer 1

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.

Answer 2

A tip for visualizing topological orders of (directed acyclic) graphs:

You can visualize them by taking the (ordered) list of vertices, and drawing the edges of the graph between the elements. So for the first question, take the list [a c b d e], and draw out the edges (I'll follow your lead and give an illustration myself):

Notice that all edges indeed point "forward". Therefore we have, by your own definition, a topological order. As for the second part, I assume that Brian M. Scott's response suffices.