For this problem, it may help to think of a topological sort (i.e. linear extens

Question

For this problem, it may help to think of a topological sort (i.e. linear extension) of a partial order as an arrangement of all the vertices in a line subject to some constraints. Consider the following partial order on the set {A, B, C, D, E, F, G, H, J}. The partial order is described via its digraph, I have out the edges from vertices to themselves and the edges implied by transitivity. Write down a linear extension (i.e. topological sort) of the partial order. How many different linear extensions does the partial order have? Explain your answer.

Explanation / Answer

The simple concept of topological sort is that, visit an edge which is a source,
i.e., a node with no incoming edges. Mark that as visited, and remove all the
outgoing edges from that node. Proceed further like this till all nodes are visited.

So, initially the only possible source vertex is: H.
Then we could go for either G, or F. So, now the two possible paths are:
   H, G, F, or H, F, G.
Then we should go for E.
So, now the two possible paths are:
H, G, F, E, or H F, G, E.
Now we could visit any of the 4 possible vertices in any order.
So, the different possibilities at this point are: 24.
And finally the node to be reachable is A.
So, one of the path is: H, G, F, E, D, C, B, J, A.
And the number of possible paths is:
3 * 24 = 48.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.