Next: About this document ...
CS130N Problem set 7: Basic graph traversal
- 1.
- Describe the details of an O(n+m) time algorithm for computing
all connected components of an undirected Graph G with m vertices
and n edges.
- 2.
- Let T be a spanning tree produced by the DFS of a connected undirected
graph G. Argue why every edge of G, not in T, goes from a vertex
v in T to one of its ancestors, that is, it is a back edge.
- 3.
- Show that, if T is a BFS tree produced for a connected graph G, then,
for each vertex v at level i, the path of T between s and v
has i edges, and any other path of G between s and v has at
least i edges.
- 4.
- Given a tree T of n nodes the diameter of T is the length of
a longest path between two nodes of T. Give an efficient algorithm
to compute the diameter of T.
- 5.
- An independent set of an undirected graph G = (V,E) is a subset
I of V such that no two vertices in I are adjacent. That is,
if then . A maximal independent set M
is an independent set such that, if we were to add any additional
vertex to M, then it would not be independent any more. Prove that
every graph has a maximal independent set. Give an efficient
algorithm to compute the maximal independent set of a given graph G.
- 6.
- An Euler tour of a directed graph G with n vertices and
m edges is a cycle that traverses each edge of G exactly once
according to its direction. Such a tour always exists if the
in-degree equals the out-degree for every vertex in G. Describe
an O(n+m) time algorithm for finding a Euler tour of such a
graph G.
- 7.
- Let G be an undirected graph with n vertices and m edges.
Describe an O(n+m) time algorithm for traversing each edge
of G exactly once in each direction.
- 8.
- A node p of a directed graph G = (V,E) is called a sink if
for every node the edge (v,p) exists, whereas
the edge (p,v) does not exist. Describe an algorithm that can
detect the presence of a sink in G in O(n) time (n is the
number of vertices). Your algorithm should accept the graph
represented by its adjacency matrix. (Notice that the running
time O(n) for this problem is remarkable given that the
instance takes a space in merely to write down).
Next: About this document ...
Subhashis Banerjee
4/24/2001