Skip to main content
Mathematics LibreTexts

13: Euler and Hamilton

  • Page ID
    60137
  • \( \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}}\)

    Some sorts of walks through a graph are particularly important for routing problems. We will be considering some of these in this chapter

    • 13.1: Euler Tours and Trails
      To introduce these concepts, we need to know about some special kinds of walks. Recall the historical example of the bridges of Königsberg. The problem of finding a route that crosses every bridge exactly once, is equivalent to finding an Euler trail in the corresponding graph. If we want the route to begin and end at the same place (for example, someone’s home), then the problem is equivalent to finding an Euler tour in the corresponding graph.
    • 13.2: Hamilton Paths and Cycles
      Sometimes, rather than traveled along every connection in a network, our object is simply to visit every node of the network. This relates to a different structure in the corresponding graph. The definitions of path and cycle ensure that vertices are not repeated. Hamilton paths and cycles are important tools for planning routes for tasks like package delivery, where the important point is not the routes taken, but the places that have been visited.
    • 13.3: Summary
      This page contains the summary of the topics covered in Chapter 13.


    This page titled 13: Euler and Hamilton is shared under a CC BY-NC-SA license and was authored, remixed, and/or curated by Joy Morris.

    • Was this article helpful?