2k views

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

Which of the following is not a topological ordering?

1. $1$ $2$ $3$ $4$ $5$ $6$
2. $1$ $3$ $2$ $4$ $5$ $6$
3. $1$ $3$ $2$ $4$ $6$ $5$
4. $3$ $2$ $4$ $1$ $6$ $5$

edited | 2k views
0
pls explain again
0
Only 4 topological orders exist for this graph:

123456

132465

123465

132456

Go with vertex with indegree 0. Remove the vertex with all edges going from it. Repeat the procedure.

We see that $3$ cannot come at first because indegree is not $0$. So, D is the answer here.

ALL other options are in Topological order.

Only $1$ and $4$ order matter for this question.

by Veteran (63k points)
edited

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

by Active (4.5k points)
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

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.
by Loyal (7.3k points)
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)
by Active (4.2k points)