Exercises

 

1. 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.

   1. Convert from an adjacency matrix to adjacency lists.
   2. 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.
   3. Convert from an incidence matrix to adjacency lists.

2. 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.

3. 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.

4. 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.

5. (*) 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.)

6. 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.

7. 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.

8. (*) 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.
9. (*) 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.
10. (*) 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.
11. (*) 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.)
12. (*) 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.
13. (*) 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.
14. (*) (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.

15. (*) 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.
    • Suppose that each edge in the graph has a weight of zero (while non-edges have a cost of ). Assume that for all vertices (i.e. all vertices have the same cost). Give an efficient algorithm to find the cheapest path from a to b and its time complexity. For partial credit, give a less efficient but correct algorithm.
    • Now suppose that the vertex costs are not constant (but are all positive) and the edge costs remain as above. Give an efficient algorithm to find the cheapest path from a to b and its time complexity. For partial credit, give a less efficient but correct algorithm.
    • Now suppose that both the edge and vertex costs are not constant (but are all positive). Give an efficient algorithm to find the cheapest path from a to b and its time complexity. For partial credit, give a less efficient but correct algorithm.

16. (*) 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.

17. 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.

18. (**) 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.