Skip to main content
Logo image

Elementary Foundations: An introduction to topics in discrete mathematics

Jeremy Sylvestre

🔗

Section 15.1 Motivation

🔗

Example 15.1.1. Driving routes on a graph.

🔗
Looking at a map of Alberta, you might decide that there are three reasonable driving routes from Camrose to Red Deer and three reasonable driving routes from Red Deer to Drumheller. Define a graph G=(V,E) with cities as vertices and routes as edges. If we travel between Camrose, Red Deer, and Drumheller on these routes, we find that any multi-city trip is a finite sequence from V∪E which starts and ends at a vertex and alternates between vertices and edges.
Graph depicting driving routes between Camrose, Red Deer, and Drumheller.
Figure 15.1.2. Driving routes between Camrose, Red Deer, and Drumheller.
🔗
🔗
For example,
C,r1,R,r4,D,r5,R,r2,C,r3,R,r6,D
🔗
is a trip that travels back and forth between Camrose and Drumheller, via Red Deer each time, and that never uses the same route twice. Notice that we cannot extend this trip without repeating a route.
<Prev^TopNext>