Topological Sort

Question

How many Topological Orderings possible from A to H?

Comments

The answer is 80.

---

smsubham

please explain

Answer 1

For E, 4 cases are possible

Case 1: A_ _ E _ _ _ H
Here 2 for BC and 2 for DFG and DGF .....that is 2×2 =4 cases will be there

Case 2: A _ _ _ E _ _ H
Here 3! For B/C/D and 2 for FG/GF .....that is 3!×2=12 cases

Case 3:A _ _ _ _ E _ H
Here 4c2×2! For B/C and 2 case for F/G....that is 24 cases

 

How ⁴C₂ * 2 ! * 2 ! ?
There are 4 places, with in that 4 places fix B and C at any two places, it is Permutation ==> ⁴C₂ * 2 !,
now there are three places remaining in whole sequence, D should be first,remaining two places and 2 elements (G and H)
==> leads to permutation = 2!

By Multiplication rule, total = ⁴C₂ * 2 ! * 2 !

Case 4: A _ _ _ _ _ E H
Here 5c2×2! For BC and 2 cases for DFG /DGF....that is 40 cases

Overall.    80 cases are there

Comments

@Shaik Masthan boss....now solution looks much better

---

i don't know, what happened to my internet, it's delayed !

---

superb explanation bro.. thank you

Answer 2

B,C should come before E

D should come before F,G

so take B,C,E as a one type of objects (for maintaining order) and D,F and G as other type of objects.

Now B and C can come in any order, but before E so there are 2! ways and similar for F and G.

So No of ways B,C,E,D,F and G = $\frac{6!*2!*2!}{3!*3!}$ =80

Comments

See....if we have to permute ABCDEF such that order of BCD does not change it would be 6!/3!.....now we are given that order of AF should also not change that is F should come after A....then ans would be 6!/3!2!.......now we are given that in BCD Order of B and C could be changed.....then we would multiply by 2! To the ans......thats what we have done in the above eg.

---

In BCE E should come at last with B and C can interchange there position and in DFG D should be first with F and G can interchange the position that's why we have multiplied with two 2!

---

Precise solution @Dharmendra Lodhi!

Answer 3

Choose A

there will be 3 paths B,C,D but consider individually

----------------------------------------------------------------------------------------------------------------

Choose B first there will be 2 paths C and D but again  check individually

                   ----------------------------------------------------------------

                  Choose C first , there will be 2 path  D and E again check individually

                              -------------------------------------------------------

                                 Choose E first then D then there will be 2 path F and G lastly H ................................(i)

                              --------------------------------------------------------

                                 Choose D first there will be 3 path E,F,G----------------------------------------------(ii)

                --------------------------------------------------------------------------

                   Choose D first then C will be 3 paths---------------------------------------------------------------(iii)

                                                    (F,G) pair and again from last 2 pairs $2\times 2=4$-------------(iv)

                                    -----------------------------------------------------------------------------

               Similarly for $C$     , So, totally  $\left ( 2+3+3+4 \right )\times 2=24$ paths for B and C

                     ------------------------------------------------------------------------------------------

              Take D first

               there will be 4 paths but we need to break it

              ------------------------------------------------------------------------

                          take B or C and  also (B,C) pair first-------------------2 paths

                           Now will get 3 paths (E,F,G)----------------------------$\binom{3}{1}$ ways

                             Total $\binom{3}{1}\times 2=6$ ways

                 --------------------------------------------------------------------------

                           or take F first will get $2\times 2=4$ ways    [take (B,C) as a pair in $\binom{2}{1}$ ways and (E,G) as a pair]

                                                          (or) take $2\times 2=4$     [take (C,G) as a pair or (B,G as a pair)]

                                                     total $8$ ways

                  So, for D there is $6\times 8=48$ ways

Total 24+48=72 ways

Comments

But answer is 80.

https://onlinegdb.com/HyBVXi1d7

Answer 4

A______H

In between A and H you can have these 4 orders

1. BCE

2. CBE

3. DFG

4. DGF

You will notice 1 and 2 are independent of 3 and 4 and hence can be executed in parallel.

Let's find concurrent ordering between 1-3,1-4,2-3,2-4

Topological ordering = No. of possible concurrent execution ( 1-3 +1-4 + 2-3 + 2-4 )

= $^6C_3$ + $^6C_3$ + $^6C_3 $ + $^6C_3 $ = $20 + 20 + 20 +20$ = $80$