Ullman (Compiler Design) Edition 2 Exercise 5.2 Question 1 (Page No. 317)

Question

 What are all the topological sorts for the dependency graph of Fig. $5.7$? 

Answer 1

There must be only 10 toposorts possible:-
(1,2)(3,4)5,6,7,8,9 → 2!*2! = 4.
(1,2) 3,5,4,6,7,8,9 -→ 2!.
(1,3)_2_4_6,7,8,9 {here 5 has 3 choices of going in any one blank space} hence:- 3C1 = 3.
here people do mistake, as they might forget one more case that is:-
2,4,1,3,5,6,7,8,9 → 1. So total topo-sorts possible are 4+2+3+1= 10.