Exercises

1.   Consider the undirected graph shown in Figure . List the elements of and . Then, for each vertex do the following:
   1. Compute the in-degree of v.
   2. Compute the out-degree of v.
   3. List the elements of .
   4. List the elements of .

     
   Figure: Sample graphs.
   

2.   Consider the directed graph shown in Figure .
   1. Show how the graph is represented using an adjacency matrix.
   2. Show how the graph is represented using adjacency lists.
3. Repeat Exercises  and  for the directed graph shown in Figure .
4.   Consider a depth-first traversal of the undirected graph shown in Figure  starting from vertex a.
   1. List the order in which the nodes are visited in a preorder traversal.
   2. List the order in which the nodes are visited in a postorder traversal.
   Repeat this exercise for a depth-first traversal starting from vertex d.
5.   List the order in which the nodes of the undirected graph shown in Figure  are visited by a breadth-first traversal that starts from vertex a. Repeat this exercise for a breadth-first traversal starting from vertex d.
6. Repeat Exercises  and  for the directed graph shown in Figure .
7. List the order in which the nodes of the directed graph shown in Figure  are visited by a topological order traversal that starts from vertex a.
8. Consider an undirected graph . If we use a adjacency matrix A to represent the graph, we end up using twice as much space as we need because A contains redundant information. That is, A is symmetric about the diagonal and all the diagonal entries are zero. Show how a one-dimensional array of length can be used to represent G. Hint: consider just the part of A above the diagonal.
9. What is the relationship between the sum of the degrees of the vertices of a graph and the number of edges in the graph.
10. A graph with the maximum number of edges is called a fully connected graph . Draw fully connected, undirected graphs that contain 2, 3, 4, and 5 vertices.
11. Prove that an undirected graph with n vertices contains at most n(n-1)/2 edges.
12. Every tree is a directed, acyclic graph (DAG), but there exist DAGs that are not trees.
    1. How can we tell whether a given DAG is a tree?
    2. Devise an algorithm to test whether a given DAG is a tree.
13. Consider an acyclic, connected, undirected graph G that has n vertices. How many edges does G have?
14. In general, an undirected graph contains one or more connected components . A connected component of a graph G is a subgraph of G that is connected and contains the largest possible number of vertices. Each vertex of G is a member of exactly one connected component of G.
    1. Devise an algorithm to count the number of connected components in a graph.
    2. Devise an algorithm that labels the vertices of a graph in such a way that all the vertices in a given connected component get the same label and vertices in different connected components get different labels.
15. A source  in an directed graph is a vertex with zero in-degree. Prove that every DAG has at least one source.
16. What kind of DAG has a unique topological sort?
17. Under what conditions does a postorder depth-first traversal of a DAG visit the vertices in reverse topological order.
18. Consider a pair of vertices, v and w, in a directed graph. Vertex w is said to be reachable from vertex v if there exists a path in G from v to w. Devise an algorithm that takes as input a graph, , and a pair of vertices, , and determines whether w is reachable from v.
19. An Eulerian walk  is a path in an undirected graph that starts and ends at the same vertex and traverses every edge in the graph. Prove that in order for such a path to exist, all the nodes must have even degree.
20. Consider the binary relation defined for the elements of the set as follows:

    

    How can we determine whether is a total order?

21. Show how the single-source shortest path problem can be solved on a DAG using a topological-order traversal. What is the running time of your algorithm?
22. Consider the directed graph shown in Figure . Trace the execution of Dijkstra's algorithm as it solves the single-source shortest path problem starting from vertex a. Give your answer in a form similar to Table .

      
    Figure: Sample weighted graphs.
    

23. Dijkstra's algorithm works as long as there are no negative edge weights. Given a graph that contains negative edge weights, we might be tempted to eliminate the negative weights by adding a constant weight to all of the edge weights to make them all positive. Explain why this does not work.
24. Dijkstra's algorithm can be modified to deal with negative edge weights (but not negative cost cycles) by eliminating the known flag and by inserting a vertex back into the queue every time its tentative distance decreases. Explain why the modified algorithm works correctly. What is the running time of the modified algorithm?
25. Consider the directed graph shown in Figure . Trace the execution of Floyd's algorithm as it solves the all-pairs shortest path problem.
26. Prove that if the edge weights on an undirected graph are distinct, there is only one minimum-cost spanning tree.
27.   Consider the undirected graph shown in Figure . Trace the execution of Prim's algorithm as it finds the minimum-cost spanning tree starting from vertex a.
28. Repeat Exercise  using Kruskal's algorithm.
29. Do Exercise .

Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.