8.1k views

Consider the following directed graph:

The number of different topological orderings of the vertices of the graph is _____________.

edited | 8.1k views
0

Although people have provided very good solution. But before looking at them think about  -

1. Counting and Discounting method of Permutation and combination. OR
2. Construct permutation tree. Desired answer could be obtained via any one of them.

PS: Same methods  are used in below mentioned solutions.

+1

The topological ordering should start with a and end with f. Just one possibility here.

For the four remaining places in between; b should come before c, and d should come before e.

b __ __ __

b can be at the first position, and c can be anywhere in the remaining three positions => 3.

__ b __ __

b can be at the second position, and therefore c should be in one of the later two spots only. => 2

__ __ b __

b can be at the third position, and therefore c gets the last position. => 1.

Total = 6 cases. (Sum rule)

Now, after filling in b and c, only two spots would remain. d and e must fill those two spots in their predetermined order.

So, 6*1 = 6. (Product rule)

Hence, 6

Here, start with $a$ and end with $f$.
$$a \;\_ \; \_ \; \_ \; \_ \; f$$
Blank spaces are to be filled with $b$, $c$, $d$, $e$ such that $b$ comes before $c$, and $d$ comes before $e$.
Number of ways to arrange $b$, $c$, $d$, $e$ such that $b$ comes before $c$ and $d$ comes before $e$, will be =  $4!/(2!*2!) = 6$
by Loyal (9.7k points)
edited
+1
Can you apply standard algorithm and than can you prove your answer???
0
there are some other cases like d comes before b
0
d comes before b is an option meaning d can come even after b.
+2

we have $a$ _ _ _ _ $f$

So we have to fill these spaces with $b,c,d,e$ such that $b \rightarrow d$ and $d \rightarrow e$

We use $\binom{4}{2}$ to pick the spots for  $b \rightarrow d$ and $d$  and $e$ can be filled in one way

so we get 6 ways
+23

If we apply BFS to find topological sort, then we can also count all topological ordering with some order.

Topological sort using BFS.

Step 1: Pick any vertex 'v', whose in-degree is zero. (There is at least one vertex who has in-degree zero, if not then you can not find any topological sort (Why? Think !) ).

Step 2: Print 'v'. Remove the vertex 'v' and all edges coming out of it.

Step 3: Repeat step 2 and 3, till all the vertices are printed.

To find all topological sort, At any point, whenever we have 2 or more choices to pick the vertex 'v', whose in-degree is 0. Then we need to consider all the cases one by one.

Example as in this graph.

Vertex A has in-degree 0, no other vertex has in-degree zero. So we have only 1 choice.
Pick A, print A, remove A and all its out-going edges.

Output: A _ _ _ _ _ _

At this point, the graph will look like this.

Now we have two choices who has in-degree zero, b and d, we will consider both one by one.

If we pick b, remove b and all out-going edges.

Output: A B _ _ _ _

(Case of choosing D after A (instead of B), will be discussed later).

Now C and D have in-degree zero.

If we pick C, then
Output: A B C _ _ _
Now, Only D has in-degree 0, We pick D, then E, then F.
Output: A B C D E F

If we pick D after we have picked B, then
Output: A B D _ _ _
Now we have two choices, C and E
Output: A B D C E F
Output: A B D E C F.

Now we got 3 output sequence (when we have chosen B after A).

What if we have chosen D after A, we still have to count these sequences. Try to count will our self you will get 3 more sequences.

If you understood this try for this graph with this method, you will get 13 topological sorts for this graph.

Image source: Geekforgeeks

0

any other simpler method because this method take lots of time?

+2
@Hemant Parihar I understood your approach, but I am not clear with why do we call it as Topological BFS?? Since BFS typical implementation follows FIFO order so when 'b' is removed , making indegree of 'c' and 'd' as 0, then as per queue, 'd' MUST be evaluated prior to 'c' but here we have choices of both.So how its an application of BFS????...plz explain

And if we say it a pure bfs implementation than, will that give all possible orderings??
0

@Shaik Masthan I forgot the method you told and that question.

+1

you may directly check in my answers list !

https://gateoverflow.in/253496/number-of-topological-order

0

What you are suggesting works for weighted graph but for unweighted graphs we can fill the queue in any order.

In topological sorting all nodes are like tasks and edges show the dependency among the tasks.

Node i to j an edge is there means task i must complete before task j.(in the mean time some other task may get complete after task i and before task j..but task i and j sequence need to be maintained)

Here in following 6 ways all the 6 tasks can get completed.

by Boss (23.9k points)
edited
0
indeed a best reference @rajesh sir
0
Rajesh How did u prepare this graphical answer. Plz explain
0
thanks sir ..grt method
0
0
Bruteforce Method-

a bdce f

a bdec f

a dbce f

a dbec f

a bcde f

a debc f
by Active (4k points)
edited
0
2*2*2=6 ??
0
sorry :)
–1 vote

this is according to me I think it is 8 I may be wrong

by (175 points)
edited
0
in second last one.. f cannot occur before b and c occur,, hence it is wrong