Homework 14
due Mon 3/11 in class

Treat the problems listed below as modeling problems — you don't need to give an efficient algorithm as asked for in the problem, but you should explain how to model the problem as a graph problem:

1. What do the vertices of the graph represent? The edges? What is the solution to the problem in terms of the graph?

2. Is the graph undirected or directed? Weighted or unweighted? (If weighted, what do the weights represent?) Simple or not simple? Sparse or dense? Cyclic or acyclic? Embedded or topological? Implicit or explicit? Labeled or unlabelled? Provide a brief explanation with each answer.

1. ADM 7-13, page 238.

2. ADM 7-30, page 240.