retagged by
28,245 views
61 votes
61 votes

Consider the following directed graph:

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

retagged by

5 Answers

Best answer
116 votes
116 votes
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$
edited by
96 votes
96 votes

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.

 

edited by
Answer:

Related questions

85 votes
85 votes
18 answers
1
Sandeep Singh asked Feb 12, 2016
35,083 views
Let $G$ be a complete undirected graph on $4$ vertices, having $6$ edges with weights being $1, 2, 3, 4, 5,$ and $6$. The maximum possible weight that a minimum weight s...
31 votes
31 votes
5 answers
2
21 votes
21 votes
7 answers
3
pC asked Dec 21, 2015
7,772 views
Consider the DAG with $V = \{1,2,3,4,5,6\}$ shown below.Which of the following is not a topological ordering?$1$ $2$ $3$ $4$ $5$ $6$$1$ $3$ $2$ $4$ $5$ $6$$1$ $3$ $2$ $4$...
0 votes
0 votes
0 answers
4