When the DFS-based topological ordering algorithm described in class is given an input graph that is not acyclic, it outputs the vertices that belong to a single cycle in the graph, and it ignores any other cycles that might exist. Suppose that, instead, we want to list all the vertices that belong to at least one cycle. Describe how to do this efficiently using a different DFS-based algorithm. (If it helps simplify the problem, you may assume that every cycle has at least two vertices.)
How many different topological orderings does the graph shown below have? List them all.
- What is the minimum number of layers needed in a layered drawing of the graph shown below? Draw the graph with this many layers.
- How many layers would be needed if we limited the number of vertices in each layer to two? Again, draw the graph with this many layers.
Find a directed acyclic graph G on four vertices with the property that G, the transitive closure of G, and the transitive reduction of G are all different from each other. Draw all three of these graphs.