833 views

2 Answers

Best answer
3 votes
3 votes
From the graph we can find that there is a path from $A$ to every vertex $except$ $B$ and $C$. So  A can come in positions $1,2$ or $3$ in the sort. Other positions in the first 3 will be occupied by either $B$ or $C$, since there exists a path from $B$ and $C$ to every other vertex other than $A$.

There is a path from $B$ to $C$, so $B$ $can$ $not$ occupy position $3$. For the same reason, $C$ can not occupy position $1$.

So, $A \rightarrow 1,2$ or $3$
$B \rightarrow 1,2$
$C \rightarrow 2,3$

Thus possible orderings of these $3$ vertices are
When $A$ is in position $1 \rightarrow ABC$ only
When $A$ is in position $2 \rightarrow BAC$ only
When $A$ is in position $3 \rightarrow BCA$ only

$D$ will always occupy position $4$ since there exists a path from $D$ to every other vertex except $A,B$ and $C$.

Remaining vertices are $E,F$ and $G$.
There is $no$ path from $F$ to $E$ or $F$ to $G$, and hence $F$ can occupy positions $5,6$ or $7$.
There is a path from $E$ to $G$. so $E$ $can$ $not$ occupy the $last$ position. For the same reason, $G$ can not occupy position $5$.

So, $E \rightarrow 5,6$
$F \rightarrow 5,6$ or $7$
$G \rightarrow 6,7$

Thus possible orderings of these $3$ vertices are

When $F$ is in position $5 \rightarrow FEG$ only
When $F$ is in position $6 \rightarrow EFG$ only
When $F$ is in position $7 \rightarrow EGF$ only

So, total number of possible orderings are $3$ x $3 = 9$.

They are:

$ABC$ $D$ $FEG$, $ABC$ $D$ $EFG$,​​​​​​ $ABC$ $D$ $EGF$

$BAC$ $D$ $FEG$, $BAC$ $D$ $EFG$, $BAC$ $D$ $EGF$

$BCA$ $D$ $FEG$, $BCA$ $D$ $EFG$, ​​​​​​​$BCA$ $D$ $EGF$
selected by

Related questions

3 votes
3 votes
0 answers
1
Balaji Jegan asked Sep 7, 2018
779 views
How many Topological Orderings possible?
20 votes
20 votes
1 answer
2
Lakshman Bhaiya asked Oct 16, 2018
5,126 views
Find the number of Topological order(sort) in the given graph?$(1)$$(2)$
2 votes
2 votes
0 answers
3