GATE CSE 2007 | Question: 5

Question

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

Which of the following is not a topological ordering?

• A. $1$ $2$ $3$ $4$ $5$ $6$
• B. $1$ $3$ $2$ $4$ $5$ $6$
• C. $1$ $3$ $2$ $4$ $6$ $5$
• D. $3$ $2$ $4$ $1$ $6$ $5$

Comments

pls explain again

---

Only 4 topological orders exist for this graph:

123456

132465

123465

132456

Answer 1

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.

Answer 2

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

Answer 3

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.

Answer 4

One of Good definition of Topological sorting is that  if in the the Graph $G$ there are two vertices $u,$  $v$  and  there is an edge between    $u\underset{}{\rightarrow}v$  so in topological ordering $u$ must appear before $v$ .

Now see all Options satisfying the condition except the D option in which  3 is coming before 1 so its not a valid ordering .

Answer 5

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 6

Answer : Option (D)

Option D is not a valid topological sorting order as it violates the directed acyclic graph (DAG) structure, as depicted in the accompanying image.