-
Present correct and efficient algorithms to convert between the following
graph data structures,
for an undirected graph G with n vertices and m edges.
You must give the time complexity of each algorithm.
-
Convert from an adjacency matrix to adjacency lists.
-
Convert from an adjacency list to an incidence matrix.
An incidence matrix M has a row for each vertex and a column
for each edge, such that M[i,j]=1 if vertex i is part of edge j,
otherwise M[i,j] = 0.
-
Convert from an incidence matrix to adjacency lists.
-
Is the path between a pair of vertices in a minimum spanning tree
necessarily a shortest path between the two vertices in the full graph?
Give a proof or a counterexample.
-
Assume that all edges in the graph have distinct edge weights
(i.e. no pair of edges have the same weight).
Is the path between a pair of vertices in a minimum spanning tree
necessarily a shortest path between the two vertices in the full graph?
Give a proof or a counterexample.
-
Suppose G is a connected undirected graph.
An edge e whose removal disconnects the graph is called a bridge.
Must every bridge e be an edge in a depth-first search tree of G, or can
e be a back edge?
Give a proof or a counterexample.
-
(*)
In breadth-first and depth-first search,
an undiscovered node is marked discovered when it
is first encountered, and marked completely-explored when it
has been completely searched.
At any given moment, several nodes might be simultaneously in the
discovered state.
(a) Describe a graph on n vertices and a particular starting vertex v
such that during a breadth-first search starting from v,
nodes are simultaneously in the discovered state.
(b) Describe a graph on n vertices and a particular starting vertex v
such that during a depth-first search starting from v,
nodes are simultaneously in the discovered state.
(c) Describe a graph on n vertices and a particular starting vertex v
such that at some point during a depth-first search starting from v,
nodes remain undiscovered, while nodes
have been completely-explored.
(Note, there may also be discovered nodes.)
-
Given the pre-order and in-order traversals of a binary
tree, is it possible to reconstruct the tree?
If so, sketch an
algorithm to do it. If not, give a counterexample. Repeat the
problem if you are given the pre-order and post-order traversals.
-
Suppose an arithmetic expression is given as a tree.
Each leaf is an integer and each internal node is one of the
standard arithmetical operations
(+,-,*,/).
For example, the expression 2+3*4+(3*4)/5 could be represented by
the tree in Figure (a).
Figure: Expression 2+3*4+(3*4)/5 as a tree and a DAG.
Give an O(n) algorithm for evaluating such an expression, where there are
n nodes in the tree.
-
(*)
Suppose an arithmetic expression is given as a DAG (directed acyclic
graph) with common subexpressions removed.
Each leaf is an integer and each internal node is one of the
standard arithmetical operations
(+,-,*,/).
For example, the expression 2+3*4+(3*4)/5 could be represented by
the DAG in Figure (b).
Give an O(n+m) algorithm for evaluating such a DAG, where there are
n nodes and m edges in the DAG.
Hint: modify an algorithm for the tree case to achieve the desired efficiency.
-
(*)
Given an undirected graph G with n vertices and m edges,
and an integer k, give an O(m+n)
algorithm that finds the maximum induced
subgraph H of G such that each vertex in H has degree , or
prove that no such graph exists.
An induced subgraph F=(U,R) of a graph G=(V,E) is a subset of U
of the vertices V of G, and all edges R of G such that both vertices
of each edge are in U.
-
(*)
An articulation vertex of a graph G is a vertex
whose deletion disconnects G.
Let G be a graph with n vertices and m edges.
Give a simple O(n+m) algorithm for finding a vertex of G that is not
an articulation vertex, i.e. whose deletion does not disconnect G.
-
(*)
Following up on the previous problem, give an O(n+m)
algorithm that finds a deletion order for the n vertices such
that no deletion disconnects the graph.
(Hint: think DFS/BFS.)
-
(*)
Let G be a weighted directed
graph with n vertices and m edges, where all edges have positive weight.
A directed cycle is a directed path that starts and ends at the same
vertex and contains at least one edge.
Give an algorithm to find a directed cycle in G of minimum total
weight.
Partial credit will be given for an algorithm.
-
(*)
Suppose we are given the minimum spanning tree T of a given graph G
(with n vertices and m edges)
and a new edge e=(u,v) of weight w that we will add to G.
Give an efficient algorithm to find the minimum spanning tree of the graph
G + e.
Your algorithm should run in O(n) time to receive full credit, although
slower but correct algorithms will receive partial credit.
-
(*)
(a) Let T be a minimum spanning tree of a weighted graph G.
Construct a new graph G' by adding a weight of k to every edge of G.
Do the edges of T form a minimum spanning tree of G'?
Prove the statement or give a counterexample.
(b) Let describe a shortest weighted path between
vertices and t of a weighted graph G.
Construct a new graph G' by adding a weight of k to every edge of G.
Does P describe a shortest path from to t in G'?
Prove the statement or give a counterexample.
-
(*)
In certain graph problems, vertices have can have weights instead of or in
addition to the weights of edges.
Let be the cost of vertex v, and the cost of the edge
(x,y).
This problem is concerned with finding the cheapest path between vertices
a and b in a graph G.
The cost of a path is the sum of the costs of the edges and vertices
encountered on the path.
-
(*)
Devise and analyze an algorithm that takes a weighted graph G and
finds the smallest change in the cost of a non-MST edge that
causes a change in the
minimum spanning tree of G.
Your algorithm must be correct and run in polynomial time.
-
An arborescence of a directed graph G is a rooted tree such that there
is a directed path from the root to every other vertex in the graph.
Give an efficient and correct algorithm to test whether
G contains an arborescence,
and its time complexity.
-
(**)
The war story of Section describes an algorithm
for constructing the dual graph of the triangulation efficiently,
although it does not guarantee linear time.
Give a worst-case linear algorithm for the problem.