Homework 4

Due Thursday, July 15th @ 8pm

Reminder: homeworks must be turned in electronically

  1. Vocab: define and give an example (where appropriate) of each of the following graph-related terms:
    1. Vertex
    2. Edge
    3. Directed Graph
    4. Undirected Graph
    5. Weighted edge
    6. Unweighted edge
    7. Cyclic graph
    8. Acyclic graph
    9. Tree
    10. Forest
    11. Connected graph
    12. DAG
    13. Partial Order
    14. Path
    15. Tour
    16. Spanning Tree
    17. Vertex Cover
    18. Hamiltonian Cycle
  2. Compare and contrast (which is not the same as define, I'm looking for some thought here) the Adjacency-List representation and the Adjacency-Matrix representation of a graph
  3. The diameter of a tree is given by the maximum-length shortest-path distance between any two nodes. (That is, the longest shortest-path in the tree.)
    1. Is diameter a well-defined concept for an arbitrary graph? Why or why not?
    2. Give an algorithm to compute the diameter of a tree. You may utilize other graph algorithms discussed in class.
  4. An Eulerian Tour of a connected, directed graph is a cycle that traverses each edge of the graph exactly once, although it may revisit vertexes.
    1. Prove that a graph has an Eulerian tour if and only if in-degree(v) == out-degree(v) for each vertex v in the graph.
    2. Give an O(E)-time algorithm to find an Eulerian tour of a graph if one exists.
  5. The Bathsheba Day Spa has recently become popular with Hollywood celebrities. One day, k celebrities inform the spa that they are coming in and submit a list of the massage specialists they will accept. The spa employs a n massage specialists, so each celebrity has chosen a subset of n. Each specialist can only massage one celebrity per day. As k can be larger than n, there are certainly instances of this problem where not all celebrities can be admitted, but the spa would like to maximize the number of celebrities that can be served.

    Show how this can be easily solved using network flow.