Networks: Circuits and Paths
In Unit 1 we looked at connected graphs and how to figure out if they have Euler paths or circuits. An Euler path travels through every edge in a graph exactly once, and an Euler circuit does the same but loops back to where you started. We also covered Hamilton paths and circuits which are a bit different since those require visiting every vertex exactly once instead of every edge. A big part of the unit was seeing how these ideas actually show up in real life situations like routing and scheduling problems.
Euler Path / Circuit
- Uses every edge exactly once
- 0 odd vertices: Circuit
- 2 odd vertices: Path
- 4+ odd vertices: Neither
Hamilton Path / Circuit
- Visits every vertex exactly once
- Doesn't need to use every edge
- Circuit means you return to start
- Good for finding shortest routes
Page 1
Page 2
Page 3
Page 1: Euler Circuits (01 Evaluate)
Page 2: Circuits Application Quiz
Page 3: Circuits Paths Practice Quiz
Google Maps and Graph Theory
Google Maps is a good real life example of graph theory because every location is basically a vertex and every road between them is an edge with a weight representing distance or time. When you put in multiple stops it finds the most efficient route to hit all of them, which is pretty much the same thing as a Hamilton path. It picks the shortest way to get everywhere without having to backtrack or repeat roads.