528 views

No of topological sortings

retagged | 528 views
0
There is no confusion in B->D->F

everything lies on A,C,E

so considered ACE, but not ECA like possibilities

now 15 coming

i am getting 15

corret me if i am wrong
+1
I am getting 15 ??
0
me too getting 15
0
i am also getting 15
0

Im getting 6 only !
Where am I doing wrong ?

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

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

• E-F-A-B-D-C
• E-F-C-D-A-B
+4
There are $8$ possibilities starting with $A$.
You are missing ::
(starting with A)
A-C-E-B-D-F
A-B-E-C-D-F + many more

Starting with A = 8, with C = 4, with E = 3 $\Rightarrow$ Total = $15$
And E-F-A-B-D-C is not a topological sort.
0
Any good resouces to learn this topic ?
+6
1. draw the graph
2. See How many vertices have in-degree $0$
3. start with any vertex with in-degree $0$,note it down.
4. Remove that vertex and associated edges
5. Next see how many vertices now with in-degree $0$ after removal of that vertex and associated edeges.
6. Go to step 3 and repeat till the end of all vertices.

While performing these steps we have to consider all available options .

+1
Thank you so much :)
0
is there any efficient way using combinatorics? i solved it and it took around 4 min. for me to get the answer. i don't want it to happen in exam.
0
topological order is sub part of of bfs

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
0
now C can be anywere after D, it is not after, it should be "before" I guess.
0
Yup.. Editing..

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
+1
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
I am also getting 15.

1
2