This week we will be finishing up with Euler circuits and 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. 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.
Don't forget to keep up with the homework on WebWork and the associated worksheets. Once you complete a worksheet, you should take it to the CAS to grade and correct your work. Make sure that you mark your mistakes and correct it with a different color writing utensil. I will collect all the graded/corrected worksheets in class on Tuesdays.
Challenge Problem: (Due Tuesday, January 30) The picture below is the floor plan for the Second Level of the Nelson-Atkins Museum in Kansas City. Doorways are represented by a break in the wall. Is it possible to start in one room on this floor, travel through every doorway, closing the door behind you, and return to where you started? Use graph theory to answer this question. Your solution should include a graph, explain how the graph is related to the floor plan, and explain how you used graph theory to determine if such a path exists. If the path exists, give it; otherwise explain why it is not possible. (https://www.nelson-atkins.org/museum-map/)
Hamiltonian circuits and paths were much easier for me to understand. I actually enjoyed doing these because it was clearer to see what i was looking for. -Annaleece Lackey 110E Sec.7
ReplyDeleteHamiltonian Method was easier to me than Euler because there were other ways to figure out the problem in faster ways. Maybe because Euler was the first graphing Theory we learned it was going to be harder but I just honestly felt more comfortable with Hamiltonian than I did Euler.
ReplyDeleteHamiltonian circuits and paths were easier to understand than Euler paths and circuits. It is more clear in what you are looking for and easier to find the solution.
ReplyDelete