GATE CSE 2016 Set 1 | Question: 11

Question

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

Comments

The best method to find Topological Sort w/o any doubt: All Topological Sorts of a Directed Acyclic Graph - GeeksforGeeks

---

for undirected graph what is the answer can anybody tell it

---

@anshul7 read this https://joshhug.gitbooks.io/hug61b/content/chap21/chap211.html

Answer 1

Here, start with $a$ and end with $f$.
$$a \;\_ \; \_ \; \_ \; \_ \; f$$
Blank spaces are to be filled with $b$, $c$, $d$, $e$ such that $b$ comes before $c$, and $d$ comes before $e$.
Number of ways to arrange $b$, $c$, $d$, $e$ such that $b$ comes before $c$ and $d$ comes before $e$, will be =  $4!/(2!*2!) = 6$

Comments

meghna What you are suggesting works for weighted graph but for unweighted graphs we can fill the queue in any order.

---

Hi what will be  the formula if there were additional edges between vertices 'b' to 'e' and 'd' to 'c' ??

Can we apply this formula in generalized way ?

Thanks

---

can you please expline why (4!/2!) i got whay 4! but not why 4!

Answer 2

In topological sorting all nodes are like tasks and edges show the dependency among the tasks.

Node i to j an edge is there means task i must complete before task j.(in the mean time some other task may get complete after task i and before task j..but task i and j sequence need to be maintained)

Here in following 6 ways all the 6 tasks can get completed.

 

Comments

indeed a best reference @rajesh sir

---

Rajesh How did u prepare this graphical answer. Plz explain

---

thanks sir ..grt method

---

nice approach @rajesh pradhan

---

nice answer sir

---

Thank you @Rajesh Sir...

---

Best approach _/\_

Answer 3

Bruteforce Method-

a bdce f

a bdec f

a dbce f

a dbec f

a bcde f

a debc f

Comments

2*2*2=6 ??

---

sorry :)

---

nice

Answer 4

Check