5
$\begingroup$

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

enter image description here

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:

enter image description here

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

$G_2$:

enter image description here

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
$\endgroup$
2
  • 1
    $\begingroup$ Upvoted since you brought such nice illustrations with you, that is appreciated :) $\endgroup$
    – MonadBoy
    Oct 20, 2015 at 22:05
  • $\begingroup$ 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! $\endgroup$
    – lucidgold
    Oct 20, 2015 at 22:09

2 Answers 2

4
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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):

enter image description here

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.

$\endgroup$
1
  • $\begingroup$ Upvated for a nice explanation! $\endgroup$
    – lucidgold
    Oct 20, 2015 at 23:15

Not the answer you're looking for? Browse other questions tagged .