retagged by
7,772 views
21 votes
21 votes

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$
retagged by

7 Answers

Best answer
31 votes
31 votes

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.

edited by
6 votes
6 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
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.
4 votes
4 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)
Answer:

Related questions

31 votes
31 votes
5 answers
1
61 votes
61 votes
5 answers
2
Sandeep Singh asked Feb 12, 2016
28,253 views
Consider the following directed graph:The number of different topological orderings of the vertices of the graph is _____________.
0 votes
0 votes
0 answers
3
0 votes
0 votes
0 answers
4
admin asked Jan 5, 2019
207 views
The Adjacency matrix of a directed graph $\text{G}$ is given below.$\begin{array} {} & a & b & c & d & e & f & g & h & i \\ a & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ b & ...