Week 2: Graph Theory - Hamiltonian Paths and Circuits

This week we will be moving into Hamiltonian Paths and Circuits and weighted graphs.  A weighted graph is just a graph with numbers (weights) on the edges.  Our goal will be to use weighted graphs and Hamiltonian circuits to solve the Traveling Salesman Problem that we discussed last week.  We will see three algorithms for solving this: The Nearest Neighbor Algorithm, The Side-Sorted (or Best Edge) Algorithm, and the Repetitive Nearest Neighbor Algorithm.  We will also discuss how to solve this using Brute Force.  You will need to memorize each of these algorithms.  We will end the week with a discussion of trees and spanning trees. 

Don't forget to keep up with the homework on WebWork.

Challenge Problem: The picture below is the floor plan for a section of prison rooms.  If all the doors are open, is it possible for a guard to enter this section at the entrance, pass through each door locking it behind him, and then exit without ever having to open a door that has been previously locked?  Answer by turning this into a graph theory question.  You may describe your graph by giving the vertices and edges or post a picture of your graph in your blog.  Your solution should include a path in the graph you create.