MA-351 Homework 2

Due at 4:59pm in my mailbox in SAS 3151, Thursday, October 6, 2009


Calculations necessary for these problems may be done either by hand or with Maple. Solutions may be submitted in person in class, or you may email an ASCII text, Maple Worksheet (.mws), html, or postscipt/pdf-formatted document to me.
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, Problems 10 on page 59.