DSC 40B – Theoretical Foundations of Data Science II

Problems tagged with "topological sorting"

Problem #113

Consider the graph $G = (V, E)$ with $V = \{a, b, c\}$ and $E = \{(a, b)\}$.

How many valid topological sorts of this graph are there?

Solution

Problem #160

Let $G = (V,E)$ be the directed graph with $V = \{a, b, c, d, e\}$ and $E = \{(a, b), (a, c), (a, d), (b, e), (c, e), (d, e)\}$. How many valid topological sorts of $V$ are there?

Solution