MA-351 Homework 2

Due at 4:59pm in my mailbox in SAS 3151, Tuesday, October 4, 2011


All solutions must be submitted in hardcopy either to me in class or placed in my mailbox. Note my office hours on my schedule.

  1. DMM, §2.3, Problem 1 on page 49 for digraph (a) only.

  2. Consider the n by n grid graph: n vertices in each of n rows and each of n columns arranged as a grid, and edges between neighboring vertices on rows and columns (excluding the wrap-around edges in the toric mesh).
    1. What is the diameter of this graph?
    2. From the top left vertex to the bottom right vertex, how many shortest paths are there? Please explain.

  3. DMM, §2.4, Problem 10 on page 59.