CompSci 163/265, Spring 2016, Homework 3

  1. Find a directed acyclic graph $G$ with three vertices and exactly three different topological orderings. List the three topological orderings of your graph.

  2. Let's say that a graph is "accessible" if it contains a vertex $v$ that can reach all the other vertices. Suppose that we want to design a certifying algorithm for whether a given directed acyclic graph is accessible. If the graph is accessible, the algorithm should output a vertex that can reach all the others; testing whether this is true is easy. If the graph is not accessible, what simple structure can we find that can be easily checked and guarantees that it is not accessible? (Hint: look at the numbers of incoming edges of each vertex.)

  3. Let $G$ be a directed acyclic graph with $n$ vertices. How many strongly connected components can $G$ have?

  4. (163 students:) Give pseudocode for an algorithm that takes as input a directed graph $G$ and a list $L$ of the vertices of $G$, and verifies that $L$ is a topological ordering of $G$. You may assume that each vertex of $G$ appears exactly once in $L$.

    (265 students:) Give pseudocode for an algorithm that takes as input a directed graph $G$ and a list of vertices $L$, and verifies that $L$ is a topological ordering of $G$. You should not assume that $L$ will always be a listing of the vertices of $G$; that is one of the things your algorithm should check.