Friday 25 January 2013
Question 1: Marks 10
A depth-first forest classifies the edges of a graph into tree,
back, forward, and cross edges. A breadth-first tree can also be used to
classify the edges reachable from the source of the search into the same four
categories.
a. Prove that in a breadth-first search of an undirected graph,
the following properties hold:
1. There
are no back edges and no forward edges.
2. For
each tree edge (u, v), we have d[v] = d[u] + 1.
3. For
each cross edge (u, v), we have d[v] = d[u] or d[v] = d[u] + 1.
b. Prove that in a breadth-first search of a directed graph, the
following properties hold:
1. There
are no forward edges.
2. For
each tree edge (u, v), we have d[v] = d[u] + 1.
3. For
each cross edge (u, v), we have d[v] ≤ d[u] + 1.
4. For
each back edge (u, v), we have 0 ≤ d[v] ≤ d[u].
Question 2: Marks 5
Explain how a vertex u of a directed graph can end up in a
depth-first tree containing only u, even though u has
both incoming and outgoing edges in G.
Question 3: Marks 5
Give a counterexample to the conjecture that if there is a path
from u to v in a directed graph G, then any depth-first search must result in
d[v] ≤ f[u].
