This
week we will be finishing up with Euler circuits and moving into Hamiltonian Paths and Circuits and weighted graphs. Fleury's algorithm will give us a systematic way to find an Euler circuit in a graph that contains one. Not every graph has an Euler circuit, but we can Eulerize a graph by duplicating existing edges in such a way that the resulting graph contains an Euler circuit. Why do you think it might be useful to Eulerize a graph?
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. I will collect all the graded/corrected worksheets in class on the day of the unit exam.
Challenge
Problem: (Due Monday, January 30) The
picture below is the floor plan for the Plaza 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.
Not quite. When we Eulerize, we are copying an existing edge from the graph. In applications, we can think of using this "new" edge as just going back over the original edge.
ReplyDeleteThe one thing I always fiend kind of frustrating in math classes is that we always have to learn how to brute force it or the hardest way to solve the problem. Then they tell you how to do it the right/easy way. It makes sense I guess, but I always get messed up with the two or more different ways to solve.-Ian Fletcher
ReplyDeletesection 4
DeleteWith the Hamiltonian circuits, brute force is the only way to guarantee that you've found the lowest weight Hamiltonian circuit. The other methods we talk about give good approximations but don't promise to be the best. We start with brute force so that you'll appreciate how much faster the other methods are.
DeleteHow might you use this information at home?
ReplyDeleteThis comment has been removed by the author.
ReplyDeletewhen using the Eulerize can we go over the same edge?
ReplyDelete_Dominique Payne
With an Euler circuit you travel each edge exactly once. (So no repetition.) When you Eulerize a graph to make it contain an Euler circuit, you make copies of existing edges, so when you make your Euler circuit, you'll use those copies, which you can think of as repeating just those edges that have been duplicated.
DeleteDoes an euler circuit require all of the vertices to be even like a ham circuit?
ReplyDelete-Zane Bembrick
You might want to review Euler's Theorem. The theorem tells us that all the vertices in a graph must be even for it to contain an Euler circuit. We don't have a rule that checks degrees of the vertices to determine if a graph has a Hamiltonian circuit.
DeleteI found it interesting that the Hamiltonian circuit only depends on if it goes through all the vertices once. Which means you dont have to have and odd or even - Roemello Whirley
ReplyDelete