October 5, 2023
October 5, 2023
October 5, 2023
###### NTA-UGC-NET 2021 Dec & 2022 June Paper-1
October 5, 2023
 Question 61

Consider the DAG with Consider 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
Question 61 Explanation:
The process to find topological order is,
(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.
Correct Answer: D
Question 61 Explanation:
The process to find topological order is,
(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.
##### Tulika Lodh
0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!