Reference Topics 9-1

An historical reference, along with a solution and interesting links for the Konigsberg bridge problem is found at this site:
http://mathforum.org/isaac/problems/bridgesol1.html

This site provides a thorough overview of the Traveling Salesperson Problem (TSP):
http://www.nist.gov/dads/HTML/travelingSalesman.html

This site provides a TSP problem … See the whole entry

Reference Topics 9-2

A historical reference, along with a solution and interesting links for the Konigsberg bridge problem is found at this site:
http://mathforum.org/isaac/problems/bridgesol1.html

This site provides a nice discussion of minimum spanning trees.
http://www.people.vcu.edu/~gasmerom/MAT131/mst.html

This is a nice interactive demonstration of Krukal’s … See the whole entry

Section 9.1: Euler Circuits and Hamiltonian Cycles

9.1 Outline

  1. Euler circuits
    1. Konigsberg bridge problem
    2. definition of a graph (or a network)
    3. traversable network
    4. degree of a vertex
    5. Euler circuit
    6. odd/even vertex
    7. connected network
    8. Euler’s circuit theorem
  2. Applications of Euler circuits
    1. supermarket problem
    2. police patrol problem
    3. floor-plan problem
See the whole entry