Register

Topology

• edited by
1,362 views
2 votes
2 votes

How many topological sorts of the following directed graph are possible?

 

• edited by
User Avatar

2 Answers

Best answer
3 votes
3 votes
The topological sorts can exchange the position of any pair node which have no directed path between them.  So nodes (b,c) , (e,f) , (h,i) are interchangeable as there is no path between them .  So for each pair there are 2 permutation so total no of permutations are 2^3 = 8
• selected by
User Avatar
3 votes
3 votes
Total 8 are possible...

To reach at D we have two paths

a-b-c-d and a-c-b-d

Now to reach at G we have again 4 paths..

a-b-c-d-e-f-g , a-b-c-d-f-e-g and

a-c-b-d-e-f-g , a-c-b-d-f-e-g

To reach at j we have 8 paths same as above...

So 8 would be the ans...

We can also do directly..
• edited by
User Avatar
Voting & Accepting an answer helps improve the community
← PreviousNext →
← Previous in categoryNext in category →

Related questions

0 votes
0 votes
1 answer
1
Arjun asked Feb 16
703 views
GATE DS&AI 2024 | Question: 41
​​​​​​Consider the directed acyclic graph (DAG) below: Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the DAG? $\text{P Q R S T U V}$ $\text{P R Q V SUT}$ $\text{P Q R S V U T}$ $\text{P R Q S V T U}$
​​​​​​Consider the directed acyclic graph (DAG) below:Which of the following is/are valid vertex orderings that can be obtained from a topological sort of the...
User Avatar
0 votes
0 votes
0 answers
2
GO Classes asked Feb 4
131 views
Memory Based GATE DA 2024 | Question: 18
Consider a directed acyclic graph (DAG) with vertices labeled as P, Q, R, S, T, U, and V. Which of the following sequences represents a possible topological sort of the graph? PRQVSUT PQRSVUT PQRSTUV PRQSVUT
Consider a directed acyclic graph (DAG) with vertices labeled as P, Q, R, S, T, U, and V. Which of the following sequences represents a possible topological sort of the g...
User Avatar
Link Copied!