0
$\begingroup$

I am reading Algorithms by Dasgupta et al and the graph section provides an example graph and mentions that there are 4 orderings with one of them being B, A, D, C, E, F.

graph

Are the other 3?

  • B, A, D, C, F, E
  • B, D, A, C, E, F
  • B, D, A, C, F, E
$\endgroup$
1
$\begingroup$

A source is a vertex with in-degree zero.

An order of the vertices is a topological order if deleting the vertices in that order deletes only sources.

Hence, you can verify that an order is topological by deleting one and one vertex, and never deleting a vertex with an in-edge.

Your answer is correct, the topological orders are B,{A,D},C,{E,F}, where you can choose the order inside the braces, i.e., there are four of them.

$\endgroup$
1
$\begingroup$

You can answer your own question by checking whether, for each edge $(u,v)$ of the graph, $u$ appears before $v$ in each of the three candidate topological orders that you listed.

$\endgroup$
6
  • $\begingroup$ What do you mean by candidate topological order? $\endgroup$ – heretoinfinity Feb 1 at 13:03
  • $\begingroup$ I mean that you can check each of the 3 additional topological orders that you listed to see if its actually a valid topological order. $\endgroup$ – Steven Feb 1 at 13:26
  • $\begingroup$ I don't get your answer in your post (not comment). Regarding the comment, I have done checking and I am uncertain and would like to clarify before I misunderstand the rest of the chapter. I am new to this. $\endgroup$ – heretoinfinity Feb 1 at 14:01
  • $\begingroup$ You are uncertain on the truth value of the statement "for each edge $(u,v)$ in the graph, $u$ appears before $v$ in all the orders given in the question" ? $\endgroup$ – Steven Feb 1 at 16:08
  • $\begingroup$ Yes, I am uncertain $\endgroup$ – heretoinfinity Feb 1 at 17:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.