Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Exercises

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

       figure55288
    Figure: Sample graphs.

  2.   Consider the directed graph tex2html_wrap_inline71881 shown in Figure gif.
    1. Show how the graph is represented using an adjacency matrix.
    2. Show how the graph is represented using adjacency lists.
  3. Repeat Exercises gif and gif for the directed graph tex2html_wrap_inline71903 shown in Figure gif.
  4.   Consider a depth-first traversal of the undirected graph tex2html_wrap_inline71881 shown in Figure gif 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 tex2html_wrap_inline71881 shown in Figure gif 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 gif and gif for the directed graph tex2html_wrap_inline71903 shown in Figure gif.
  7. List the order in which the nodes of the directed graph tex2html_wrap_inline71903 shown in Figure gif are visited by a topological order traversal that starts from vertex a.
  8. Consider an undirected graph tex2html_wrap_inline69997. If we use a tex2html_wrap_inline70537 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 tex2html_wrap_inline71933 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, tex2html_wrap_inline69997, and a pair of vertices, tex2html_wrap_inline71973, 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 tex2html_wrap_inline60772 defined for the elements of the set tex2html_wrap_inline65990 as follows:

    displaymath71879

    How can we determine whether tex2html_wrap_inline60772 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 tex2html_wrap_inline71985 shown in Figure gif. 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 gif.

       figure55619
    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 tex2html_wrap_inline70999 and by inserting a vertex back into the queue every time its tentative distance tex2html_wrap_inline71001 decreases. Explain why the modified algorithm works correctly. What is the running time of the modified algorithm?
  25. Consider the directed graph tex2html_wrap_inline71985 shown in Figure gif. 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 tex2html_wrap_inline71999 shown in Figure gif. Trace the execution of Prim's algorithm as it finds the minimum-cost spanning tree starting from vertex a.
  28. Repeat Exercise gif using Kruskal's algorithm.
  29. Do Exercise gif.

next up previous contents index

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