20 votes

Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.

Which of the following is not a topological ordering?

- $1$ $2$ $3$ $4$ $5$ $6$
- $1$ $3$ $2$ $4$ $5$ $6$
- $1$ $3$ $2$ $4$ $6$ $5$
- $3$ $2$ $4$ $1$ $6$ $5$

26 votes

Best answer

5 votes

*choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges.*

after that there are two possibilities remove one by one either vertex 2 or 3. after that there is one possibility remove vertex 4 .after that two possibilities remove either vertex 5 or 6 one by one. the order of vertex we get is called topological ordering.

here a,b,c are correct but d is wrong. so d is ans

5 votes

The arrow represents which comes after or which comes before i.e a-->b means that a must come before b or b must come after a

Now jump to the given diagram, as it is clear that

i) 2 and 3 must come after 1

ii) 4 must come after 2 and 3 so obvious comes after 1 also

iii) 5 and 6 must come after 4 so obvious must comes after 1,2 and 3 also.

Now follow this step and check with the given options

Hence option D is not correct as 3 does not comes before 1 (point no. i)

NOTE: (2,3) and (5,6) are at same level, therefore their positions can be interchange as in option (A and B) position of 2 and 3 interchanged.

Now jump to the given diagram, as it is clear that

i) 2 and 3 must come after 1

ii) 4 must come after 2 and 3 so obvious comes after 1 also

iii) 5 and 6 must come after 4 so obvious must comes after 1,2 and 3 also.

Now follow this step and check with the given options

Hence option D is not correct as 3 does not comes before 1 (point no. i)

NOTE: (2,3) and (5,6) are at same level, therefore their positions can be interchange as in option (A and B) position of 2 and 3 interchanged.

3 votes

choose vertex in the graph which has 0 indegree. now see graph has vertex 1 with 0 indegree so remove this along with its edges. See option D) it is starting with vertex 3 which is not having indegree as zero so it can not be answer ..

Therefore option D)

Therefore option D)

0 votes

(i) Go with vertex with indegree 0.

(ii) Then remove that vertex and also remove the edges going from it.

(iii) Repeat again from (i) till every vertex is completed.

Now we can see that in option (D), '3' is given first which is not possible because indegree of vertex '3' is not zero.

Hence option **(D) is not topological ordering.**