Find the Number of possible topological sort

Question

Question

Find the Number of possible topological sort of following diagram defined on relation $\preceq$ (not interested in what this relation is)

My Answer

I am getting possible Topological sort

$T1 \preceq T4 \preceq T5 $

$T1 \preceq T2 \preceq T3 \preceq T5 $

$T1 \preceq T3 \preceq T5 $

Am i right or missing anything?

Thanks!

Answer 1

Every total order must include all the relationships in the graph, plus additional ones to make it into a total order. Note that $T_1$ must come first: $T_1$ must come before $T_2, T_3, T_4$, and $T_3$ must come before $T_5$. Note also that $T_2$ must come second, since it must come before $T_3, T_4, T_5$. Finally, note that $T_5$ must come last, since both $T_3$ and $T_4$ must come before $T_5$. Hence the only answers are

$$T_1 < T_2 < T_3 < T_4 < T_5$$

and

$$T_1 < T_2 < T_4 < T_3 < T_5$$