Which of the following lists are possible topological sorts

Which of the following lists are possible topological sorts of the graph G below?

1. f, b, c, e, a, d

2. e, f, b, a, d, c

3. c, e, b, f, a, d

4. e, c, f, b, d, a

5. e, b, f, a, c, d

6. f, a, d, c, e, b

Select all that apply and explain, thank you.

Solution

Topological sort  of a DAG is a linear ordering of its vertices such that for every directed edge uv from vertex u to vertex v, u comes before v in the ordering.

1. The lsit is not possible because there is a directed edge from e to b thus e should come before b, but in the list b comes before e. So the list is not valid.

2. The list or sequence is possible because there is no edge comming towards e and f so e and f can appear before any other node. There is edge from e to b, so b can come after e. Since all nodes which have edge towards a i:e b,e,f are already in the list thus a can appear after them. Since c is an isolated node so it can appear anywhere in the list.

3. The list is possible as it follows the condition of topological sort discussed above.

4. The list is not possible because d cannot come before a as there is edge from a to d.

5. The lis is possible as it follows the topological sort condition.

6. The list is not possible because a canot come before e and b