edited by
2,021 views
3 votes
3 votes

No of topological sortings

edited by

5 Answers

3 votes
3 votes
If we choosen node A then there are Three way to select next node either node C , node E , node B ie 3! . next when we choose node A as well as any of node C , E , B the there are two way for select next node either node E , node B ie 2!.

Hence After select node A no of way is = 3! + 2!

                                                         = 8

( A--B--C--E--D--F

  A--B--C--D--E--F

  A--B--E--C--D--F  

  A--C--E--B--D--F

  A--C--B--E--D--F  

  A--C--B--D--E--F

  A--E--C--B--D--F

  A--E--B--C--D--F)

If we choosen node E then there are Two way to select next node either node A , node C ie 2! . next when we choose node E as well as any of node A , C  the there are one way for select next node either node A , node C ie 1!.

Hence After select node A no of way is = 2! + 1!

                                                         = 3

(E--A--C--B--D--F

E--A--B--C--D--F

E--C--A--B--D--F)

but when select node C there are only two way to select next node , either node A , node E ie 2! .  next when we choose node C as well as any of node  A , E the there are two way for select next node  ie 2! .

Hence After select node C no of way is = 2! + 2!

                                                         = 4

(C--A--B--D--E--F

C--A--B--E--D--F

C--A--E--B--D--F

C--E--A--B--D--F)

so , Total topological sort = 8 + 3 + 4 = 15
edited by
2 votes
2 votes
A -> B -> D -> F sequence is fixed .now C can be anywere before D.and E can be anywhere after F
So, C can be at any of 3 place (shown with " _ " )

 _A_B_D ->F
take case 1: C at first position CABDF now Ecan be at

_C_A_B_D_ ->F at 5 places
similarly for remaining 2 cases as

_A_C_B_D_ ->F and 5 places

  _A_B_C_D_ ->F 5 places

total 15 no. of topological sorting sequence
edited by
1 votes
1 votes
there are two possibility without e.

ac->b->d->f

 

a->bc->d->f

Now with e how many possibility we check by inserting e at every position in above two cases

                                ac->b->d->f

e at position :        |     |   |   |

                               3!     2!    2!           = 10

                               a->bc->d->f

e at position :       |    |     |   |

                               2!    3!   2!                =10

so total =10+10=20
0 votes
0 votes
Please check:

ABDF are fixed. Remaining 2 are to be placed: _A_B_D_F_

Nothing comes after F, and E<F and C<D

=> _A_B_D_F

If E comes before 4th dash: 1st, 2nd, 3rd dash: Each has 2 choices => 8 ways

If E comes at 4th dash, 1st,2nd,3rd dash have 1 choice each => 3*1*1 = 3 ways

Ans = 8+3= 11

Related questions

2 votes
2 votes
1 answer
1
4 votes
4 votes
2 answers
2
target2017 asked Jan 30, 2017
2,025 views
Please explain how they merged.(Modified)
4 votes
4 votes
3 answers
4