Chapter 8b: Hamiltonian and Weighted Graphs PDF

SECTION 2 SECTION 2 CHAPTER 8b. The Mathematics of Graph– Hamiltonian & Weighted Graphs Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives...

SECTION 2 SECTION 2 CHAPTER 8b. The Mathematics of Graph– Hamiltonian & Weighted Graphs Core Idea “Mathematics creates connections and fosters efficiency through visual tools like graphs and algorithms.” learning objectives 1. define a Hamiltonian circuit and describe weighted graphs; 2. find a Hamiltonian circuit in a graph; and 3. use algorithms to find a Hamiltonian circuit in a weighted graph. HAMILTONIAN CIRCUIT It is a cycle where the each vertex is traversed exactly once and starts and ends at the same vertex. HAMILTONIAN PATH It is a path where each vertex is traversed exactly once and starts and ends at the different vertices. HAMILTONIAN A graph is Hamiltonian if and only if it has a Hamiltonian circuit. Historical background William Rowan Hamilton (1805-1865) – Irish mathematician who studied ”Hamiltonian” circuits HAMILTONIAN CIRCUIT It is a cycle where the vertices are traversed exactly once that starts and ends at the same vertex. It is a path where the vertices are traversed exactly HAMILTONIAN PATH once that starts and ends at different vertices. Example: Consider 𝒖𝟏 as a starting vertex. 𝒖𝟏 𝒖𝟏 Hamiltonian path Hamiltonian circuit 𝒗𝟏 𝒗𝟏 𝒖𝟓 𝒖𝟐 𝒖𝟓 𝒖𝟐 𝒗𝟓 𝒗𝟐 𝒗𝟓 𝒗𝟐 𝒗𝟒 𝒗𝟑 𝒗𝟒 𝒗𝟑 𝒖𝟒 𝒖𝟑 𝒖𝟒 𝒖𝟑 𝑢1 − 𝑢2 − 𝑢3 − 𝑣3 − 𝑣2 − 𝑢1 − 𝑢2 − 𝑢3 − 𝑣3 − 𝑣2 − 𝑣1 − 𝑣5 − 𝑣4 − 𝑢4 − 𝑢5 𝑣1 − 𝑣5 − 𝑣4 − 𝑢4 − 𝑢5 − 𝑢1 Example: (Example, Pg 244) Portland-Boise-Butte-Salt Lake City-Reno-Sacramento-Portland Example: San Francisco-Boston-Atlanta-New York-Los Angeles-Phoenix-Dalas-San Francisco (Check your progress 1, Pg 244) Example: San Francisco-Boston-New York-Atlanta- Dalas-Phoenix-Los Angeles-San Francisco (Check your progress 1, Pg 244) MORE EXAMPLES Find a Hamiltonian circuit for each graph. a. b. MORE EXAMPLES Find a Hamiltonian circuit for each graph. a. b. WEIGHTED GRAPHS It is a graph where each edge is associated with a value called weight. Each edge’s weight represents the cost to travel along that edge. The cost could be distance, length, time, money, or some other measure. The cost depends on the underlying problem. WEIGHTED GRAPHS It is a graph where each edge is associated with a value called weight. (Example 2, Pg 245) WEIGHTED GRAPHS It is a graph where each edge is associated with a value called weight. (Example 2, Pg 245) ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm It is an algorithm that finds a solution to problems in the shortest time possible. It makes us choose the cheapest option at every chance we get. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm Use the greedy algorithm to find a Hamiltonian circuit in the weighted graph shown. (Example 3, Pg 247) ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm Consider starting at A. The smallest edge incident to A is 4. Hightlight AD. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm At D, the smallest edge incident is 2. Hightlight DB. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm At B, the smallest edge incident is 5. Hightlight BF. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm At F, the smallest edge incident is 7. However, D has been visited. Choose the next smallest weight. That is 10. Hightlight FE. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm At E, the smallest edge incident that has not been connected is C. Hightlight CE. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm All vertices has been visited. Hence, we follow the third/last step. End the circuit at the starting vertex. Hightlight AC. ALGORITHMS IN COMPLETE GRAPHS The Greedy Algorithm Hence, the Hamiltonian circuit is A-D-B-F-E-C-A. The weight of the circuit is 4+2+5+10+6+15 = 42. ALGORITHMS IN COMPLETE GRAPHS (Check your progress 3 & 4) A. Use the Greedy algorithm and the Edge-picking algorithm to find a Hamiltonian circuit. State the corresponding weight. Which gave a more efficient route? Why? ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm Use the edge-picking algorithm to find a Hamiltonian circuit in the weighted graph shown. (Example 3, Pg 247) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm The smallest weight is 2. Highlight BD. (Example 3, Pg 247) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm The next smallest weight is 4. Highlight AD. (Example 3, Pg 247) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm The next smallest weight is 5 which appears twice. Consider both. Highlight AE and BF. (Example 4, Pg 248) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm The next smallest weight is 6 which appears twice. We cannot consider BC since B is already incident to 2 edges. Hence, only highlight EC. (Example 4, Pg 248) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm All vertices has been visited. Marked the edge that connects the 2 vertices that are still incident to a single edge. These are F and C. Hence, hightlight FC. (Example 4, Pg 248) ALGORITHMS IN COMPLETE GRAPHS The Edge-Picking Algorithm Hence, the Hamiltonian circuit is A-D-B-F-C-E-A or A-E-C-F-B-D-A The weight of the circuit is 4+2+5+14+6+5 = 36. (Example 4, Pg 248) ALGORITHMS IN COMPLETE GRAPHS (Check your progress 3 & 4) A. Use the Greedy algorithm and the Edge-picking algorithm to find a Hamiltonian circuit. State the corresponding weight. Which gave a more efficient route? Why? ALGORITHMS IN COMPLETE GRAPHS Use the Greedy algorithm and the Edge-picking algorithm to find a Hamiltonian circuit. State the corresponding weight. Which gave a more efficient route? Why? ALGORITHMS IN COMPLETE GRAPHS B. Trace a Hamiltonian circuit from each graph. End of Discussion…