Skip to main content
Mathematics LibreTexts

15.1: Motivation

  1. Last updated
  2. Save as PDF
  • Page ID
    83478

    • \( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

    Example \(\PageIndex{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 \cup E\) which starts and ends at a vertex and alternates between vertices and edges.

    clipboard_e9984a3fcc7fd6bdba127a81ae5aacdef.png
    Figure \(\PageIndex{1}\): Driving routes between Camrose, Red Deer, and Drumheller.

    For example,

    \begin{equation*} C, r_1, R, r_4, D, r_5, R, r_2, C, r_3, R, r_6, D \end{equation*}
    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.

    This page titled 15.1: Motivation is shared under a GNU Free Documentation License 1.3 license and was authored, remixed, and/or curated by Jeremy Sylvestre via source content that was edited to the style and standards of the LibreTexts platform; a detailed edit history is available upon request.