|
|
Graph Theory with
|
|
|
|
Graph Theory with
|
|
The Traveling Salesperson versus the Road Inspector
Each of the two people has the same map. The difference is that the salesperson must visit every town, and the inspector must check every road.
The questions are:
Can the traveling salesperson visit each town (vertex) without having to drive through the same town more than once?
Can the road inspector start at one town, travel across each road (edge) without having to do it more than once, and return to the starting place?
Assignment Exercises
Readings Bello & Britton,
Sections 7.6 Aand
Graphs, Games, and the NCTM
Standardshttp://www.c3.lanl.gov/mega-math
/workbk/graph/grnctm.html
Web Resources These web resources have links to
graph theory sites.
...
2. The Hamiltonian Grid Problem and then post to the discussion forum called Hamiltonian Grids a real-world situation in which finding a Hamiltonian circuit on an m x n grid graph would represent a solution to the problem?
...
...
4. Networks are used to plan house/museum tours by superimposing a network on top of the floor plan where the rooms are considered to be the vertices and the doorways as the edges as seen in this model below:
Use this idea for solving pp. 503, Ex. 13, 16, 19, 20.
...
5. Draw trees with 2, 3, 4, 5, and 6 vertices. What is the relationship between the number of vertices in a tress and the numbers of edges?
...
6. Solve the heating plant network problem.
...
7. Solve the rail network problem.
...
8. What is the problem with solving the 3 Utilities network?
http://cut-the-knot.com/do_you_know/3Utilities.htmlwith 2 answers/explanations from Ask Dr., Math at:http://forum.swarthmore.edu/dr.math/problems/tone.7.19.96.html
http://forum.swarthmore.edu/dr.math/problems/chris.07.15.99.html
...
9. Develop a problem where you would use network theory. Which type of network would you use?
Könisberg Bridge Original jpeg
HTTP://www-groups.dcs.st-and.ac.uk/~history/Diagrams/Konigsberg_colour.jpegCourse material on Euler, Hamiltonian and Trees with Kruskal's algorithm -with excellent explanations and drawings
http://www.sa.ua.edu/ctl/math103/Cut-the-Knot web site on Geometry - interactive Internet applets for a variety of geometry questions at all levels
http://cut-the-knot.com/geometry.htmlCut-the -Knot section on Graphs with an interactive applet - starts with the Könisberg Bridge problem
and also has an applet where you can draw your own networks and try to connect them
http://cut-the-knot.com/do_you_know/graphs.htmlGraph Theory - excellent middle school introduction to graph theory
http://www.c3.lanl.gov/mega-math/workbk/graph/graph.htmlwith The Mathematics of Graphs and their Games
http://www.c3.lanl.gov/mega-math/workbk/graph/grbkgd.htmland More Games using Graphs
http://www.c3.lanl.gov/mega-math/workbk/graph/grother.htmlGraph Theory Interactive Tutorials - (you need to sign in, but you can put any name and password -
it just is there to allow you to stop and then continue later) -
presents ideas in small pieces and then gives a quiz on the idea - it will not allow you to go on until you pass the quiz
http://www.utm.edu/departments/math/graph/with the interactive Introduction to Graph Theory
http://www.utm.edu/cgi-bin/caldwell/tutor/departments/math/graph/introand Euler Circuits starting with the Königsberg bridge
http://www.utm.edu/cgi-bin/caldwell/tutor/departments/math/graph/eulerMinimal Spanning Trees - lecture on this topic
http://www.cs.byu.edu/courses/cs236/lectures/GRAPHS4/Graphs4.htmlA Walk in the Park by: Susan K. Eddins - another version of the Könisberg Bridge Problem
but in Barcelona, Spain from the Illinois Mathematics and Science Academy
http://www.imsa.edu/edu/math/journal/volume4/webver/eulpath.html
Syllabus | Home | Assignments | Bibliography
