The Gateway to Computer Science Excellence

+24 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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.3k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.5k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,647 questions

56,503 answers

195,502 comments

100,865 users