MadeEasy CBT 2017: Algorithms - Graph Algorithms

Question

No of topological sortings

Comments

Answer i think is 20 mentioned in image

---

hmmm yes I'm wrong

---

topological order is sub part of of bfs

Answer 1

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

Comments

When we start with A then we can delete B immediately but if we start with E, we cannot delete B immediately... So Number of ways starting with E will be less than that of A. Please correct me if I am wrong.

---

Tthanks , you are correct.

Answer 2

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

Comments

now C can be anywere after D, it is not after, it should be "before" I guess.

---

Yup.. Editing..

Answer 3

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

Comments

I got 15 brother

btw didn't understood you approach ,

                                 ac->b->d->f

e at position :        |       |      |    |

                               3!     2!    2!           = 10

you wanted to say that : ac b d fe also a topological order ???

but it's not right ???

 

---

@Magma

$15$ is the right answer.

see this https://gateoverflow.in/109278/made-easy-cbt-2017-q22

---

Hmm thanks

---

I have big problem to count number of topological ordering,can you tell me how to count all possible ordering?

Answer 4

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

Comments

No.

C comes at 1st position ->3 ways to choose for E between 2,3,4

C comes at 2nd pposition ->3 ways to chosse for E between 1,3,4

C comes at 3rd position -> 3 ways to choose for E between 1,2,4

Total = 9