MYP Extended Mathematics Paths and Cycles Notes

1. Networks (graphs) give a powerful way to model journeys, routes, and connections.
2. In this section you learn to classify paths, cycles, and special routes that use edges or vertices in controlled ways.
3. These ideas underpin problems such as planning a postal delivery route (the Chinese Postman Problem) and planning a shortest "visit-everywhere-once" tour (the Traveling Salesman Problem).

Paths, Trails, And Cycles Describe Different Kinds Of Journeys

1. A path is a sequence of vertices where consecutive vertices are joined by an edge.
2. Depending on the context, we care about whether edges or vertices are repeated.

1. A cycle is a special type of closed path.
2. Cycles are important because many real-world routes must return to the start (for example, a delivery van that must return to the depot).

Euler Routes Are About Using Every Edge

An Eulerian route is about covering every edge of a graph.

To decide whether these routes exist, you only need two properties: whether the graph is connected and how many vertices have odd degree.

Traversability Depends On Odd Vertices

1. A graph is called traversable if you can draw it without lifting your pen and without retracing an edge.
2. A connected graph:
   1. with only even-degree vertices is traversable and has an Eulerian circuit (you can start anywhere and finish where you started)
   2. with exactly two odd-degree vertices is traversable and has an Eulerian trail (any such trail must start at one odd vertex and finish at the other)
   3. with more than two odd-degree vertices has no Eulerian circuit or Eulerian trail, so it is non-traversable without repeating edges