advertisement

Routing Problems Examples Euler Circuit Problems Unicursal Drawings Graph Theory Spring 2015 Mathematics in Management Science Routing Problems Examples of routing problems • Mail/Garbage collection • Meter reading • Snow plowing • Security patrol Routing Problems Existence question Is an actual route possible? Optimization question Of all the possible routes, which one is the optimal route? Euler Circuit Problem These are special Routing Problems. The common thread is so-called exhaustion requirement; the route must ‘go everywhere’. Typically want to begin & end at same location. We’ll see that ECPs are easy to solve! Unicursal Drawings Want to trace each drawing w/o lifting pencil or retracing any of the lines. If we begin & end in the same place, call it a closed unicursal tracing; otherwise an open unicursal tracing. Graphs • A graph is a finite set of dots and connecting links. • The dots are called vertices. • The links are called edges. • The valence of a vertex is the number edges that meet there. • Vertices can be even or odd depending on their valence. Example Paths and Circuits • A path is a finite sequence of adjacent edges on a graph that joins two vertices. • A circuit is a path that begins and ends at the same vertex. • A graph is connected if every vertex can be joined to every other vertex by a path. Euler Paths and Circuits • An Euler path is a path that traverses each edge exactly once. • An Euler circuit is a circuit that traverses each edge exactly once. Euler Circuit Problem Questions: • Do all graphs have Euler circuits? Answer: No. • Can we tell which graphs have an Euler circuit and which don’t? Answer: Yes! First, the graph must be all one piece--- it must be connected. Next,… Euler’s Circuit Theorem A graph has an Euler circuit if and only if the graph is connected, and, all its vertices have even valence. Any odd vertex means NO Euler circuit. Once we know they exist: How do we find Euler circuits?