#set document(title: "12.9 Traveling Salesperson Problem", author: "OpenStax / XYZ Homework")
#set page(width: 8.5in, height: auto, margin: 1in)
#import "@preview/cetz:0.5.2"
#set text(font: ("STIX Two Text", "Libertinus Serif", "New Computer Modern"), size: 10.5pt, lang: "en")
#show math.equation: set text(font: ("STIX Two Math", "New Computer Modern Math"))
#set par(justify: true, leading: 0.62em, spacing: 0.9em)
#set enum(spacing: 1.1em)   // room between list items so tall inline fractions don't collide
#set list(spacing: 1.1em)
#set table(stroke: 0.5pt + rgb("#c7ccd3"))

#let BLUE = rgb("#183B6F")     // brand navy — section bars + example/solution labels (white on navy 11.09:1)
#let ORANGE = rgb("#A94509")   // brand primary-700 — AA-safe deep orange for TEXT (5.93:1 on white; raw brand #F37021 is 2.94:1 and must never carry text)
#let RED = rgb("#DC2626")      // brand error-600
#let GREEN = rgb("#059669")    // brand success-600 (decoration only; small green text uses green-text #007942)

#show heading.where(level: 1): it => block(width: 100%, above: 0pt, below: 16pt,
  fill: gradient.linear(BLUE, rgb("#2C5AA0")), inset: (x: 14pt, y: 12pt), radius: 3pt,
  text(fill: white, weight: "bold", size: 19pt, it.body))
#show heading.where(level: 2): it => block(width: 100%, above: 18pt, below: 10pt,
  fill: BLUE, inset: (x: 10pt, y: 6pt), radius: 2pt,
  text(fill: white, weight: "bold", size: 12pt, it.body))
#show heading.where(level: 3): it => text(fill: ORANGE, weight: "bold", size: 12.5pt, it.body)
#show heading.where(level: 4): it => text(fill: BLUE, weight: "bold", size: 10.5pt, it.body)

#let examplebox(label, title, body) = block(width: 100%, breakable: true,
  fill: rgb("#EFF1F5"), stroke: 0.5pt + rgb("#CFDDF0"), radius: 4pt, inset: 10pt,
  above: 12pt, below: 12pt)[
  #block(below: 6pt)[#box(fill: BLUE, inset: (x: 6pt, y: 2pt), radius: 2pt,
    text(fill: white, weight: "bold", size: 8.5pt, label)) #h(0.4em) #strong[#title]]
  #body]

// rail = decorative left rule (raw brand token); labelcolor = AA-safe label text shade
#let notebox(label, rail, labelcolor, tint, body) = block(width: 100%, breakable: true, fill: tint,
    stroke: (left: 3pt + rail), inset: (left: 10pt, rest: 8pt), radius: (right: 4pt),
    above: 11pt, below: 11pt)[
    #text(fill: labelcolor, weight: "bold", size: 7.5pt, tracking: 0.5pt)[#upper(label)]
    #linebreak() #body]

#let solutionbox(body) = block(above: 4pt, below: 8pt)[
  #text(fill: BLUE, weight: "bold", size: 8.5pt)[Solution] #linebreak() #body]

#let figph(msg) = block(width: 100%, height: 60pt, fill: rgb("#f6f7f9"),
  stroke: (paint: rgb("#c7ccd3"), dash: "dashed"), radius: 4pt, inset: 10pt)[
  #align(center + horizon, text(fill: rgb("#889"), style: "italic", size: 9pt, msg))]

// Standardize inlined figure sizes: measure the natural CeTZ canvas, then scale to a
// consistent envelope (aspect-aware; see build_typst.py FIG_* constants). Unlike the
// print preamble, dimensions are FLOORED: in an editor a user can trim a figure to a
// degenerate 1-D shape (a bare line), and w/h or tw/w would then divide by zero.
#let _STD_W = 3.5
#let _WIDE_W = 5.6
#let _MAX_H = 3.4
#let _ASPECT_WIDE = 2.2
#let _UPSCALE_MAX = 1.15
#let stdfig(body) = context {
  let m = measure(body)
  let w = calc.max(m.width / 1in, 0.01)
  let h = calc.max(m.height / 1in, 0.01)
  let tw = if w / h > _ASPECT_WIDE { _WIDE_W } else { _STD_W }
  let s = calc.min(tw / w, _MAX_H / h, _UPSCALE_MAX)
  align(center, box(scale(x: s * 100%, y: s * 100%, reflow: true, body)))
}

#show figure: set block(breakable: false)
#set figure(gap: 8pt)
#show figure.caption: set text(size: 8.5pt, fill: rgb("#555"))


  
== 12.9#h(0.6em)Traveling Salesperson Problem


  #figure(figph[Three doors are shown side-by-side.], alt: "Three doors are shown side-by-side.", caption: [Each door on the route of a traveling salesperson can be represented as a vertex on a graph.])


  
    
=== Learning Objectives


    After completing this section, you should be able to:


    + Distinguish between brute force algorithms and greedy algorithms.
+ List all distinct Hamilton cycles of a complete graph.
+ Apply brute force method to solve traveling salesperson applications.
+ Apply nearest neighbor method to solve traveling salesperson applications.


  
  We looked at Hamilton cycles and paths in the previous sections Hamilton Cycles and Hamilton Paths. In this section, we will analyze Hamilton cycles in complete weighted graphs to find the shortest route to visit a number of locations and return to the starting point. Besides the many routing applications in which we need the shortest distance, there are also applications in which we search for the route that is least expensive or takes the least time. Here are a few less common applications that you can read about on #link("https://openstax.org/r/University_of_Waterloo")[a website set up by the mathematics department at the University of Waterloo in Ontario, Canada:]


  - Design of fiber optic networks
- Minimizing fuel expenses for repositioning satellites
- Development of semi-conductors for microchips
- A technique for mapping mammalian chromosomes in genome sequencing


  Before we look at approaches to solving applications like these, let's discuss the two types of algorithms we will use.


  
    
=== Brute Force and Greedy Algorithms


    An algorithm is a sequence of steps that can be used to solve a particular problem. We have solved many problems in this chapter, and the procedures that we used were different types of algorithms. In this section, we will use two common types of algorithms, a #strong[brute force algorithm] and a #strong[greedy algorithm]. A brute force algorithm begins by listing every possible solution and applying each one until the best solution is found. A greedy algorithm approaches a problem in stages, making the apparent best choice at each stage, then linking the choices together into an overall solution which may or may not be the best solution.


    To understand the difference between these two algorithms, consider the tree diagram in . Suppose we want to find the path from left to right with the largest total sum. For example, branch A in the tree diagram has a sum of #math.equation(block: false, alt: "10 plus 2 plus 11 plus 13 equals 36")[$10 + 2 + 11 + 13 = 36$].


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 0.00pt), (-86.40pt, -54.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (86.40pt, -54.00pt), stroke: 0.7pt + black)
  line((-86.40pt, -54.00pt), (-129.60pt, -108.00pt), stroke: 0.7pt + black)
  line((-86.40pt, -54.00pt), (-43.20pt, -108.00pt), stroke: 0.7pt + black)
  line((-129.60pt, -108.00pt), (-151.20pt, -162.00pt), stroke: 0.7pt + black)
  line((-129.60pt, -108.00pt), (-108.00pt, -162.00pt), stroke: 0.7pt + black)
  line((-43.20pt, -108.00pt), (-64.80pt, -162.00pt), stroke: 0.7pt + black)
  line((-43.20pt, -108.00pt), (-21.60pt, -162.00pt), stroke: 0.7pt + black)
  line((86.40pt, -54.00pt), (43.20pt, -108.00pt), stroke: 0.7pt + black)
  line((86.40pt, -54.00pt), (129.60pt, -108.00pt), stroke: 0.7pt + black)
  line((43.20pt, -108.00pt), (21.60pt, -162.00pt), stroke: 0.7pt + black)
  line((43.20pt, -108.00pt), (64.80pt, -162.00pt), stroke: 0.7pt + black)
  line((129.60pt, -108.00pt), (108.00pt, -162.00pt), stroke: 0.7pt + black)
  line((129.60pt, -108.00pt), (151.20pt, -162.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((0.00pt, 0.00pt), text(size: 9pt)[10])
  circle((-86.40pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-86.40pt, -54.00pt), text(size: 9pt)[2])
  circle((86.40pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((86.40pt, -54.00pt), text(size: 9pt)[7])
  circle((-129.60pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-129.60pt, -108.00pt), text(size: 9pt)[11])
  circle((-43.20pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-43.20pt, -108.00pt), text(size: 9pt)[15])
  circle((-151.20pt, -162.00pt), radius: 18.00pt, stroke: 0.7pt + black, fill: white)
  content((-151.20pt, -162.00pt), text(size: 9pt)[13 (A)])
  circle((-108.00pt, -162.00pt), radius: 15.50pt, stroke: 0.7pt + black, fill: white)
  content((-108.00pt, -162.00pt), text(size: 9pt)[8 (B)])
  circle((-64.80pt, -162.00pt), radius: 15.50pt, stroke: 0.7pt + black, fill: white)
  content((-64.80pt, -162.00pt), text(size: 9pt)[1 (C)])
  circle((-21.60pt, -162.00pt), radius: 15.50pt, stroke: 0.7pt + black, fill: white)
  content((-21.60pt, -162.00pt), text(size: 9pt)[6 (D)])
  circle((43.20pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((43.20pt, -108.00pt), text(size: 9pt)[3])
  circle((129.60pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((129.60pt, -108.00pt), text(size: 9pt)[4])
  circle((21.60pt, -162.00pt), radius: 18.00pt, stroke: 0.7pt + black, fill: white)
  content((21.60pt, -162.00pt), text(size: 9pt)[20 (E)])
  circle((64.80pt, -162.00pt), radius: 18.00pt, stroke: 0.7pt + black, fill: white)
  content((64.80pt, -162.00pt), text(size: 9pt)[14 (F)])
  circle((108.00pt, -162.00pt), radius: 18.00pt, stroke: 0.7pt + black, fill: white)
  content((108.00pt, -162.00pt), text(size: 9pt)[11 (G)])
  circle((151.20pt, -162.00pt), radius: 15.50pt, stroke: 0.7pt + black, fill: white)
  content((151.20pt, -162.00pt), text(size: 9pt)[5 (H)])
})]),
  alt: "A graph has 15 vertices. The vertices are labeled 1 to 15. 10 branches into 2 and 7. 2 branches into 11 and 15. 11 branches into 13 and 8. 15 branches into 1 and 6. 7 branches into 3 and 4. 3 branches into 20 and 14. 4 branches into 11 and 5. 13, 8, 1, 6, 20, 14, 11, and 5 are labeled A to H.", caption: [Points Along Different Paths],
)


    To be certain that you pick the branch with greatest sum, you could list each sum from each of the different branches:


    #emph[A]: #math.equation(block: false, alt: "10 plus 2 plus 11 plus 13 equals 36")[$10 + 2 + 11 + 13 = 36$]


    #emph[B]: #math.equation(block: false, alt: "10 plus 2 plus 11 plus 8 equals 31")[$10 + 2 + 11 + 8 = 31$]


    #emph[C]: #math.equation(block: false, alt: "10 plus 2 plus 15 plus 1 equals 28")[$10 + 2 + 15 + 1 = 28$]


    #emph[D]: #math.equation(block: false, alt: "10 plus 2 plus 15 plus 6 equals 33")[$10 + 2 + 15 + 6 = 33$]


    #emph[E]: #math.equation(block: false, alt: "10 plus 7 plus 3 plus 20 equals 40")[$10 + 7 + 3 + 20 = 40$]


    #emph[F]: #math.equation(block: false, alt: "10 plus 7 plus 3 plus 14 equals 34")[$10 + 7 + 3 + 14 = 34$]


    #emph[G]: #math.equation(block: false, alt: "10 plus 7 plus 4 plus 11 equals 32")[$10 + 7 + 4 + 11 = 32$]


    #emph[H]: #math.equation(block: false, alt: "10 plus 7 plus 4 plus 5 equals 26")[$10 + 7 + 4 + 5 = 26$]


    Then we know with certainty that branch #emph[E] has the greatest sum.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 0.00pt), (-86.40pt, -54.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (86.40pt, -54.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((-86.40pt, -54.00pt), (-129.60pt, -108.00pt), stroke: 0.7pt + black)
  line((-86.40pt, -54.00pt), (-43.20pt, -108.00pt), stroke: 0.7pt + black)
  line((-129.60pt, -108.00pt), (-151.20pt, -162.00pt), stroke: 0.7pt + black)
  line((-129.60pt, -108.00pt), (-108.00pt, -162.00pt), stroke: 0.7pt + black)
  line((-43.20pt, -108.00pt), (-64.80pt, -162.00pt), stroke: 0.7pt + black)
  line((-43.20pt, -108.00pt), (-21.60pt, -162.00pt), stroke: 0.7pt + black)
  line((86.40pt, -54.00pt), (43.20pt, -108.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((86.40pt, -54.00pt), (129.60pt, -108.00pt), stroke: 0.7pt + black)
  line((43.20pt, -108.00pt), (21.60pt, -162.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((43.20pt, -108.00pt), (64.80pt, -162.00pt), stroke: 0.7pt + black)
  line((129.60pt, -108.00pt), (108.00pt, -162.00pt), stroke: 0.7pt + black)
  line((129.60pt, -108.00pt), (151.20pt, -162.00pt), stroke: 0.7pt + black)
  circle((0.00pt, 0.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((0.00pt, 0.00pt), text(size: 9pt)[10])
  circle((-86.40pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-86.40pt, -54.00pt), text(size: 9pt)[2])
  circle((86.40pt, -54.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((86.40pt, -54.00pt), text(size: 9pt)[7])
  circle((-129.60pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-129.60pt, -108.00pt), text(size: 9pt)[11])
  circle((-43.20pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-43.20pt, -108.00pt), text(size: 9pt)[15])
  circle((-151.20pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-151.20pt, -162.00pt), text(size: 9pt)[13])
  circle((-108.00pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-108.00pt, -162.00pt), text(size: 9pt)[8])
  circle((-64.80pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-64.80pt, -162.00pt), text(size: 9pt)[1])
  circle((-21.60pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-21.60pt, -162.00pt), text(size: 9pt)[6])
  circle((43.20pt, -108.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((43.20pt, -108.00pt), text(size: 9pt)[3])
  circle((129.60pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((129.60pt, -108.00pt), text(size: 9pt)[4])
  circle((21.60pt, -162.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((21.60pt, -162.00pt), text(size: 9pt)[20])
  circle((64.80pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((64.80pt, -162.00pt), text(size: 9pt)[14])
  circle((108.00pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((108.00pt, -162.00pt), text(size: 9pt)[11])
  circle((151.20pt, -162.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((151.20pt, -162.00pt), text(size: 9pt)[5])
})]),
  alt: "A graph has 15 vertices. The vertices are labeled 1 to 15. 10 branches into 2 and 7. 2 branches into 11 and 15. 11 branches into 13 and 8. 15 branches into 1 and 6. 7 branches into 3 and 4. 3 branches into 20 and 14. 4 branches into 11 and 5. 13, 8, 1, 6, 20, 14, 11, and 5 are labeled A to H. The edges 10 to 7, 7 to 3, and 3 to 20 are highlighted. An arrow from E points to 20.", caption: [Branch #emph[E]],
)


    Now suppose that you wanted to find the branch with the highest value, but you only were shown the tree diagram in phases, one step at a time.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 0.00pt), (-21.60pt, -54.00pt), stroke: 0.7pt + black)
  line((0.00pt, 0.00pt), (21.60pt, -54.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  circle((0.00pt, 0.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((0.00pt, 0.00pt), text(size: 9pt)[10])
  circle((-21.60pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-21.60pt, -54.00pt), text(size: 9pt)[2])
  circle((21.60pt, -54.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((21.60pt, -54.00pt), text(size: 9pt)[7])
})]),
  alt: "A graph has 3 vertices. The vertices are labeled 10, 2, and 7. 10 branches into 2 and 7. The edge, 10 to 7 is highlighted.", caption: [Tree Diagram Phase 1],
)


    After phase 1, you would have chosen the branch with 10 and 7. So far, you are following the same branch. Let’s look at the next phase.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-10.80pt, 0.00pt), (-43.20pt, -54.00pt), stroke: 0.7pt + black)
  line((-10.80pt, 0.00pt), (21.60pt, -54.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((21.60pt, -54.00pt), (0.00pt, -108.00pt), stroke: 0.7pt + black)
  line((21.60pt, -54.00pt), (43.20pt, -108.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  circle((-10.80pt, 0.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-10.80pt, 0.00pt), text(size: 9pt)[10])
  circle((-43.20pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-43.20pt, -54.00pt), text(size: 9pt)[2])
  circle((21.60pt, -54.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((21.60pt, -54.00pt), text(size: 9pt)[7])
  circle((0.00pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((0.00pt, -108.00pt), text(size: 9pt)[3])
  circle((43.20pt, -108.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((43.20pt, -108.00pt), text(size: 9pt)[4])
})]),
  alt: "A graph has 5 vertices. The vertices are labeled 10, 2, 7, 3, and 4. 10 branches into 2 and 7. 7 branches into 3 and 4. The edges, 10 to 7 and 7 to 4 are highlighted.", caption: [Tree Diagram Phase 2],
)


    After phase 2, based on the information you have, you will choose the branch with 10, 7 and 4. Now, you are following a different branch than before, but it is the best choice based on the information you have. Let’s look at the last phase.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((-27.00pt, 0.00pt), (-64.80pt, -54.00pt), stroke: 0.7pt + black)
  line((-27.00pt, 0.00pt), (10.80pt, -54.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((10.80pt, -54.00pt), (-21.60pt, -108.00pt), stroke: 0.7pt + black)
  line((10.80pt, -54.00pt), (43.20pt, -108.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((43.20pt, -108.00pt), (21.60pt, -162.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  line((43.20pt, -108.00pt), (64.80pt, -162.00pt), stroke: (paint: rgb("#D62128"), thickness: 1.6pt))
  circle((-27.00pt, 0.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-27.00pt, 0.00pt), text(size: 9pt)[10])
  circle((-64.80pt, -54.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-64.80pt, -54.00pt), text(size: 9pt)[2])
  circle((10.80pt, -54.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((10.80pt, -54.00pt), text(size: 9pt)[7])
  circle((-21.60pt, -108.00pt), radius: 9.00pt, stroke: 0.7pt + black, fill: white)
  content((-21.60pt, -108.00pt), text(size: 9pt)[3])
  circle((43.20pt, -108.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((43.20pt, -108.00pt), text(size: 9pt)[4])
  circle((21.60pt, -162.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((21.60pt, -162.00pt), text(size: 9pt)[11])
  circle((64.80pt, -162.00pt), radius: 9.00pt, stroke: (paint: rgb("#D62128"), thickness: 1.4pt), fill: white)
  content((64.80pt, -162.00pt), text(size: 9pt)[5])
})]),
  alt: "A graph has 7 vertices. The vertices are labeled 10, 2, 7, 3, 4, 11, and 15. 10 branches into 2 and 7. 7 branches into 3 and 4. 4 branches into 11 and 5. The edges, 10 to 7, 7 to 4, and 4 to 11 are highlighted. 11 and 5 are labeled G and H.", caption: [Tree Diagram Phase 3],
)


    After phase 3, you will choose branch #emph[G] which has a sum of 32.


    The process of adding the values on each branch and selecting the highest sum is an example of a brute force algorithm because all options were explored in detail. The process of choosing the branch in phases, based on the best choice at each phase is a greedy algorithm. Although a brute force algorithm gives us the ideal solution, it can take a very long time to implement. Imagine a tree diagram with thousands or even millions of branches. It might not be possible to check all the sums. A greedy algorithm, on the other hand, can be completed in a relatively short time, and generally leads to good solutions, but not necessarily the ideal solution.


    #examplebox("Example 1")[Distinguishing between Brute Force and Greedy Algorithms][
A cashier rings up a sale for \$4.63 cents in U.S. currency. The customer pays with a \$5 bill. The cashier would like to give the customer \$0.37 in change using the fewest coins possible. The coins that can be used are quarters (\$0.25), dimes (\$0.10), nickels (\$0.05), and pennies (\$0.01). The cashier starts by selecting the coin of highest value less than or equal to \$0.37, which is a quarter. This leaves #math.equation(block: false, alt: "$ 0.37 minus $ 0.25 equals $ 0.12")[$"$" 0.37 − "$" 0.25 = "$" 0.12$]. The cashier selects the coin of highest value less than or equal to \$0.12, which is a dime. This leaves #math.equation(block: false, alt: "$ 0.12 minus $ 0.10 equals $ 0.02")[$"$" 0.12 − "$" 0.10 = "$" 0.02$]. The cashier selects the coin of highest value less than or equal to \$0.02, which is a penny. This leaves #math.equation(block: false, alt: "$ 0.02 minus $ 0.01 equals $ 0.01")[$"$" 0.02 − "$" 0.01 = "$" 0.01$]. The cashier selects the coin of highest value less than or equal to \$0.01, which is a penny. This leaves no remainder. The cashier used one quarter, one dime, and two pennies, which is four coins. Use this information to answer the following questions.


        + Is the cashier’s approach an example of a greedy algorithm or a brute force algorithm? Explain how you know.
+ The cashier’s solution is the best solution. In other words, four is the fewest number of coins possible. Is this consistent with the results of an algorithm of this kind? Explain your reasoning.


      
      #solutionbox[
+ The approach the cashier used is an example of a greedy algorithm, because the problem was approached in phases and the best choice was made at each phase. Also, it is not a brute force algorithm, because the cashier did not attempt to list out all possible combinations of coins to reach this conclusion.
+ Yes, it is consistent. A greedy algorithm does not always yield the best result, but sometimes it does.
]
]


    
  
  
    
=== The Traveling Salesperson Problem


    Now let’s focus our attention on the graph theory application known as the #strong[traveling salesperson problem (TSP)] in which we must find the shortest route to visit a number of locations and return to the starting point.


    Recall from Hamilton Cycles, the officer in the U.S. Air Force who is stationed at Vandenberg Air Force base and must drive to visit three other California Air Force bases before returning to Vandenberg. The officer needed to visit each base once. We looked at the weighted graph in  representing the four U.S. Air Force bases: Vandenberg, Edwards, Los Angeles, and Beal and the distances between them.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  content((21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410])
  content((21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396])
  content((-21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159])
  content((-21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106])
  content((-18.48pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439])
  content((0.00pt, 10.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[E])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[L])
})]),
  alt: "A graph represents the four California air force bases. The graph has four vertices: E, B, V, and L. The edge, E B is labeld 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles.", caption: [Graph of Four California Air Force Bases],
)


    Any route that visits each base and returns to the start would be a Hamilton cycle on the graph. If the officer wants to travel the shortest distance, this will correspond to a Hamilton cycle of lowest weight. We saw in  that there are six distinct Hamilton cycles (directed cycles) in a complete graph with four vertices, but some lie on the same cycle (undirected cycle) in the graph.


    #figure(table(
  columns: 4, align: left, inset: 6pt,
  table.header([Complete Graph], [Cycle], [Cycle], [Cycle]),
  [], [], [], [],
  [#strong[Clockwise Hamilton Cycle]], [#emph[a] → #emph[b] → #emph[c] → #emph[d] → #emph[a]], [#emph[a] → #emph[b] → #emph[d] → #emph[c] → #emph[a]], [#emph[a] → #emph[c] → #emph[b] → #emph[d] → #emph[a]],
  [#strong[Counterclockwise Hamilton Cycle]], [#emph[a] → #emph[d] → #emph[c] → #emph[b] → #emph[a]], [#emph[a] → #emph[c] → #emph[d] → #emph[b] → #emph[a]], [#emph[a] → #emph[d] → #emph[b] → #emph[c] → #emph[a]],
))


    Since the distance between bases is the same in either direction, it does not matter if the officer travels clockwise or counterclockwise. So, there are really only three possible distances as shown.


    #figure(
  stdfig([#grid(columns: 3, column-gutter: 1.2em, row-gutter: 1.6em,
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  content((21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410])
  content((21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396])
  content((-21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159])
  content((-21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106])
  content((-18.48pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439])
  content((0.00pt, 10.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[E])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[L])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  content((21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410])
  content((21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396])
  content((-21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159])
  content((-21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106])
  content((-18.48pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439])
  content((0.00pt, 10.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[E])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[L])
})],
  [#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (42.00pt, 0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((42.00pt, 0.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-42.00pt, -0.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-42.00pt, -0.00pt), (0.00pt, 42.00pt), stroke: 0.7pt + black)
  line((-42.00pt, -0.00pt), (42.00pt, 0.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  content((21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410])
  content((21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396])
  content((-21.00pt, -21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159])
  content((-21.00pt, 21.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106])
  content((-18.48pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439])
  content((0.00pt, 10.08pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[E])
  circle((42.00pt, 0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((42.00pt, 0.00pt), text(size: 9pt, fill: black)[B])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V])
  circle((-42.00pt, -0.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-42.00pt, -0.00pt), text(size: 9pt, fill: black)[L])
})]
)]),
  alt: "Three graphs represent the four California air force bases. Each graph has four vertices: E, B, V, and L. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. In the first graph, the edges, E V, and L B are in dashed lines. In the second graph, the edges, E L and B V are in dashed lines. In the third graph, the edges, E B and L V are in dashed lines.", caption: [Three Possible Distances],
)


    The possible distances are:


    #math.equation(block: true, alt: "396 plus 410 plus 106 plus 159 equals 1071; 207 plus 410 plus 439 plus 159 equals 1215; 396 plus 439 plus 106 plus 207 equals 1148")[$396 + 410 + 106 + 159 = 1071 \ 207 + 410 + 439 + 159 = 1215 \ 396 + 439 + 106 + 207 = 1148$]
    So, a Hamilton cycle of least weight is #emph[V] → #emph[B] → #emph[E] → #emph[L] → #emph[V] (or the reverse direction). The officer should travel from Vandenberg to Beal to Edwards, to Los Angeles, and back to Vandenberg.


  
  
    
=== Finding Weights of All Hamilton Cycles in Complete Graphs


    Notice that we listed all of the Hamilton cycles and found their weights when we solved the TSP about the officer from Vandenberg. This is a skill you will need to practice. To make sure you don't miss any, you can calculate the number of possible Hamilton cycles in a complete graph. It is also helpful to know that half of the directed cycles in a complete graph are the same cycle in reverse direction, so, you only have to calculate half the number of possible weights, and the rest are duplicates.


    #notebox("Formula", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
In a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices,


      - The number of distinct Hamilton cycles is #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$].
- There are at most #math.equation(block: false, alt: "the fraction open parenthesis n minus 1 close parenthesis ! over 2")[$frac(( n − 1 ) !, 2)$] different weights of Hamilton cycles.
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[TIP! When listing all the distinct Hamilton cycles in a complete graph, you can start them all at any vertex you choose. Remember, the cycle #emph[a] → #emph[b] → #emph[c] → #emph[a] is the same cycle as #emph[b] → #emph[c] → #emph[a] → #emph[b] so there is no need to list both.]
]


    #examplebox("Example 2")[Calculating Possible Weights of Hamilton Cycles][
Suppose you have a complete weighted graph with vertices #emph[N, M, O], and #emph[P].


        + Use the formula #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$] to calculate the number of distinct Hamilton cycles in the graph.
+ Use the formula #math.equation(block: false, alt: "the fraction open parenthesis n minus 1 close parenthesis ! over 2")[$frac(( n − 1 ) !, 2)$] to calculate the greatest number of different weights possible for the Hamilton cycles.
+ Are all of the distinct Hamilton cycles listed here? How do you know? #linebreak() 
    Cycle 1: #emph[N] → #emph[M] → #emph[O] → #emph[P] → #emph[N] #linebreak() 
    Cycle 2: #emph[N] → #emph[M] → #emph[P] → #emph[O] → #emph[N] #linebreak() 
    Cycle 3: #emph[N] → #emph[O] → #emph[M] → #emph[P] → #emph[N] #linebreak() 
    Cycle 4: #emph[N] → #emph[O] → #emph[P] → #emph[M] → #emph[N] #linebreak() 
    Cycle 5: #emph[N] → #emph[P] → #emph[M] → #emph[O] → #emph[N] #linebreak() 
    Cycle 6: #emph[N] → #emph[P] → #emph[O] → #emph[M] → #emph[N]
+ Which pairs of cycles must have the same weights? How do you know?


      
      #solutionbox[
+ There are 4 vertices; so, #math.equation(block: false, alt: "n equals 4")[$n = 4$]. This means there are #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis ! equals open parenthesis 4 minus 1 close parenthesis ! equals 3 times 2 times 1 equals 6")[$( n − 1 ) ! = ( 4 − 1 ) ! = 3 ⋅ 2 ⋅ 1 = 6$] distinct Hamilton cycles beginning at any given vertex.
+ Since #math.equation(block: false, alt: "n equals 4")[$n = 4$], there are #math.equation(block: false, alt: "the fraction open parenthesis n minus 1 close parenthesis ! over 2 equals the fraction open parenthesis 4 minus 1 close parenthesis ! over 2 equals the fraction 6 over 2 equals 3")[$frac(( n − 1 ) !, 2) = frac(( 4 − 1 ) !, 2) = frac(6, 2) = 3$] possible weights.
+ Yes, they are all distinct cycles and there are 6 of them.
+ Cycles 1 and 6 have the same weight, Cycles 2 and 4 have the same weight, and Cycles 3 and 5 have the same weight, because these pairs follow the same route through the graph but in reverse.
]
]


    #notebox("Checkpoint", rgb("#059669"), rgb("#007942"), rgb("#EAF3EC"))[
#emph[TIP! When listing the possible cycles, ignore the vertex where the cycle begins and ends and focus on the ways to arrange the letters that represent the vertices in the middle. Using a systematic approach is best; for example, if you must arrange the letters M, O, and P, first list all those arrangements beginning with M, then beginning with O, and then beginning with P, as we did in Example 2.]
]


    
  
  
    
=== The Brute Force Method


    The method we have been using to find a Hamilton cycle of least weight in a complete graph is a brute force algorithm, so it is called the #strong[brute force method]. The steps in the brute force method are:


    #strong[Step 1:] Calculate the number of distinct Hamilton cycles and the number of possible weights.


    #strong[Step 2:] List all possible Hamilton cycles.


    #strong[Step 3:] Find the weight of each cycle.


    #strong[Step 4:] Identify the Hamilton cycle of lowest weight.


    #examplebox("Example 3")[Applying the Brute Force Method][
On the next assignment, the air force officer must leave from Travis Air Force base, visit Beal, Edwards, and Vandenberg Air Force bases each exactly once and return to Travis Air Force base. There is no need to visit Los Angeles Air Force base. Use  to find the shortest route.


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  content((0.00pt, 74.97pt), text(font: sys.inputs.at("title-font", default: "STIX Two Text"), size: 10pt)[Five California air force bases])
  line((0.00pt, 53.97pt), (51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((51.32pt, 16.68pt), (31.72pt, -43.66pt), stroke: 0.7pt + black)
  line((31.72pt, -43.66pt), (-31.72pt, -43.66pt), stroke: 0.7pt + black)
  line((-31.72pt, -43.66pt), (0.00pt, 53.97pt), stroke: 0.7pt + black)
  line((-31.72pt, -43.66pt), (51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((0.00pt, 53.97pt), (31.72pt, -43.66pt), stroke: 0.7pt + black)
  line((0.00pt, 53.97pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((-31.72pt, -43.66pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((51.32pt, 16.68pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((31.72pt, -43.66pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  content((35.21pt, 48.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410 miles])
  content((61.53pt, -19.99pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  content((0.00pt, -49.66pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159 miles])
  content((-15.86pt, 5.15pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106 miles])
  content((9.80pt, -13.49pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439 miles])
  content((39.68pt, -0.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207 miles])
  content((-35.21pt, 48.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[370 miles])
  content((-61.53pt, -19.99pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  content((0.00pt, 16.68pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[84 miles])
  content((8.47pt, -26.77pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  circle((0.00pt, 53.97pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 53.97pt), text(size: 9pt, fill: black)[E])
  circle((51.32pt, 16.68pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((51.32pt, 16.68pt), text(size: 9pt, fill: black)[B])
  circle((31.72pt, -43.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((31.72pt, -43.66pt), text(size: 9pt, fill: black)[V])
  circle((-31.72pt, -43.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-31.72pt, -43.66pt), text(size: 9pt, fill: black)[L])
  circle((-51.32pt, 16.68pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-51.32pt, 16.68pt), text(size: 9pt, fill: black)[T])
})]),
  alt: "A graph represents the five California air force bases. The graph has five vertices: E, B, V, L, and T. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. The edge, E T is labeled 370 miles. The edge, L T is labeled 396 miles. The edge, B T is labeled 84 miles. The edge, V T is labeled 396 miles.", caption: [Distances between Five California Air Force Bases],
)


      
      #solutionbox[
#strong[Step 1:] Since there are 4 vertices, there will be #math.equation(block: false, alt: "open parenthesis 4 minus 1 close parenthesis ! equals 3 ! equals 6")[$( 4 − 1 ) ! = 3 ! = 6$] cycles, but half of them will be the reverse of the others; so, there will be #math.equation(block: false, alt: "the fraction open parenthesis 4 minus 1 close parenthesis ! over 2 equals the fraction 6 over 2 equals 3")[$frac(( 4 − 1 ) !, 2) = frac(6, 2) = 3$] possible distances.


        #strong[Step 2:] List all the Hamilton cycles in the subgraph of the graph in .


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 53.97pt), (51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((51.32pt, 16.68pt), (31.72pt, -43.66pt), stroke: 0.7pt + black)
  line((31.72pt, -43.66pt), (-31.72pt, -43.66pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-31.72pt, -43.66pt), (0.00pt, 53.97pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-31.72pt, -43.66pt), (51.32pt, 16.68pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 53.97pt), (31.72pt, -43.66pt), stroke: 0.7pt + black)
  line((0.00pt, 53.97pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((-31.72pt, -43.66pt), (-51.32pt, 16.68pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((51.32pt, 16.68pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  line((31.72pt, -43.66pt), (-51.32pt, 16.68pt), stroke: 0.7pt + black)
  content((35.21pt, 48.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[410 miles])
  content((61.53pt, -19.99pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  content((0.00pt, -49.66pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[159 miles])
  content((-15.86pt, 5.15pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[106 miles])
  content((9.80pt, -13.49pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[439 miles])
  content((39.68pt, -0.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[207 miles])
  content((-35.21pt, 48.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[370 miles])
  content((-61.53pt, -19.99pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  content((0.00pt, 16.68pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[84 miles])
  content((8.47pt, -26.77pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[396 miles])
  circle((0.00pt, 53.97pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 53.97pt), text(size: 9pt, fill: black)[E])
  circle((51.32pt, 16.68pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((51.32pt, 16.68pt), text(size: 9pt, fill: black)[B])
  circle((31.72pt, -43.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((31.72pt, -43.66pt), text(size: 9pt, fill: black)[V])
  circle((-31.72pt, -43.66pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-31.72pt, -43.66pt), text(size: 9pt, fill: black)[L])
  circle((-51.32pt, 16.68pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-51.32pt, 16.68pt), text(size: 9pt, fill: black)[T])
})]),
  alt: "A graph represents four cities. The graph has five vertices: E, B, V, L, and T. The edge, E B is labeled 410 miles. The edge, B V is labeled 396 miles. The edge, V L is labeled 159 miles. The edge, L E is labeled 106 miles. The edge, L B is labeled 439 miles. The edge, E V is labeled 207 miles. The edge, E T is labeled 370 miles. The edge, L T is labeled 396 miles. The edge, B T is labeled 84 miles. The edge, V T is labeled 396 miles. The edges, E L, L V, L B, and L T are in dashed lines.", caption: [Subgraph with Cities #emph[B, E, T], and #emph[V]],
)


        To find the 6 cycles, focus on the three vertices in the middle, #emph[B, E,] and #emph[V]. The arrangements of these vertices are #emph[BEV, BVE, EBV, EVB, VBE], and #emph[VEB]. These would correspond to the 6 cycles:


        1: #emph[T] → #emph[B] → #emph[E] → #emph[V] → #emph[T]


        2: #emph[T] → #emph[B] → #emph[V] → #emph[E] → #emph[T]


        3: #emph[T] → #emph[E] → #emph[B] → #emph[V] → #emph[T]


        4: #emph[T] → #emph[E] → #emph[V] → #emph[B] → #emph[T]


        5: #emph[T] → #emph[V] → #emph[B] → #emph[E] → #emph[T]


        6: #emph[T] → #emph[V] → #emph[E] → #emph[B] → #emph[T]


        #strong[Step 3:] Find the weight of each path. You can reduce your work by observing the cycles that are reverses of each other.


        1: #math.equation(block: false, alt: "84 plus 410 plus 207 plus 396 equals 1097")[$84 + 410 + 207 + 396 = 1097$]


        2: #math.equation(block: false, alt: "84 plus 396 plus 207 plus 370 equals 1071")[$84 + 396 + 207 + 370 = 1071$]


        3: #math.equation(block: false, alt: "370 plus 410 plus 396 plus 396 equals 1572")[$370 + 410 + 396 + 396 = 1572$]


        4: Reverse of cycle 2, 1071


        5: Reverse of cycle 3, 1572


        6: Reverse of cycle 1, 1097


        #strong[Step 4:] Identify a Hamilton cycle of least weight.


        The second path, #emph[T] → #emph[B] → #emph[V] → #emph[E] → #emph[T], and its reverse, #emph[T] → #emph[E] → #emph[V] → #emph[B] → #emph[T], have the least weight. The solution is that the officer should travel from Travis Air Force base to Beal Air Force Base, to Vandenberg Air Force base, to Edwards Air Force base, and return to Travis Air Force base, or the same route in reverse.
]
]


    
    Now suppose that the officer needed a cycle that visited all 5 of the Air Force bases in . There would be #math.equation(block: false, alt: "open parenthesis 5 minus 1 close parenthesis ! equals 4 ! equals 4 times 3 times 2 times 1 equals 24")[$( 5 − 1 ) ! = 4 ! = 4 × 3 × 2 × 1 = 24$] different arrangements of vertices and #math.equation(block: false, alt: "the fraction open parenthesis 5 minus 1 close parenthesis ! over 2 equals the fraction 4 ! over 2 equals the fraction 24 over 2 equals 12")[$frac(( 5 − 1 ) !, 2) = frac(4 !, 2) = frac(24, 2) = 12$] distances to compare using the brute force method. If you consider 10 Air Force bases, there would be #math.equation(block: false, alt: "open parenthesis 10 minus 1 close parenthesis ! equals 9 ! equals 9 times 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1 equals 362 , 880")[$( 10 − 1 ) ! = 9 ! = 9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1 = 362 , 880$] different arrangements and #math.equation(block: false, alt: "the fraction open parenthesis 10 minus 1 close parenthesis ! over 2 equals the fraction 9 ! over 2 equals the fraction 9 times 8 times 7 times 6 times 5 times 4 times 3 times 2 times 1 over 2 equals 181 , 440")[$frac(( 10 − 1 ) !, 2) = frac(9 !, 2) = frac(9 ⋅ 8 ⋅ 7 ⋅ 6 ⋅ 5 ⋅ 4 ⋅ 3 ⋅ 2 ⋅ 1, 2) = 181 , 440$] distances to consider. There must be another way!


  
  
    
=== The Nearest Neighbor Method


    When the brute force method is impractical for solving a traveling salesperson problem, an alternative is a greedy algorithm known as the #strong[nearest neighbor method], which always visit the closest or least costly place first. This method finds a Hamilton cycle of relatively low weight in a complete graph in which, at each phase, the next vertex is chosen by comparing the edges between the current vertex and the remaining vertices to find the lowest weight. Since the nearest neighbor method is a greedy algorithm, it usually doesn’t give the best solution, but it usually gives a solution that is "good enough." Most importantly, the number of steps will be the number of vertices. That’s right! A problem with 10 vertices requires 10 steps, not 362,880. Let’s look at an example to see how it works.


    Suppose that a candidate for governor wants to hold rallies around the state. They plan to leave their home in city #emph[A], visit cities #emph[B, C, D, E], and #emph[F] each once, and return home. The airfare between cities is indicated in the graph in .


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[A])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[B])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[D])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[E])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[F])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars.", caption: [Airfares between Cities #emph[A, B, C, D, E], and #emph[F]],
)


    Let’s help the candidate keep costs of travel down by applying the nearest neighbor method to find a Hamilton cycle that has a reasonably low weight. Begin by marking starting vertex as #math.equation(block: false, alt: "V sub 1")[$V_(1)$] for "visited 1st." Then to compare the weights of the edges between #emph[A] and vertices adjacent to #emph[A]: \$250, \$210, \$300, \$200, and \$100 as shown. The lowest of these is \$100, which is the edge between #emph[A] and #emph[F].


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[V1])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[B])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[D])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[E])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[F])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. The edges from A are in dashed lines. A is labeled V 1.", caption: [Finding the Second Vertex],
)


    Mark #emph[F] as #math.equation(block: false, alt: "V sub 2")[$V_(2)$] for "visited 2nd" then compare the weights of the edges between #emph[F] and the remaining vertices adjacent to #emph[F]: \$170, \$330, \$150 and \$350 as shown. The lowest of these is \$150, which is the edge between #emph[F] and #emph[D].


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[350])
  circle((0.00pt, 42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[V 1])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[B])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[D])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[E])
  circle((-36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[V 2])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. An edge from E to F is labeled 350 dollars. The edges from F are in dashed lines. A is labeled V 1. F is labeled V 2.", caption: [Finding the Third Vertex],
)


    Mark #emph[D] as #math.equation(block: false, alt: "V sub 3")[$V_(3)$] for "visited 3rd." Next, compare the weights of the edges between #emph[D] and the remaining vertices adjacent to #emph[D]: \$120, \$310, and \$270 as shown. The lowest of these is \$120, which is the edge between #emph[D] and #emph[B].


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 71.76pt), (62.15pt, 35.88pt), stroke: 0.7pt + black)
  line((0.00pt, 71.76pt), (62.15pt, -35.88pt), stroke: 0.7pt + black)
  line((0.00pt, 71.76pt), (0.00pt, -71.76pt), stroke: 0.7pt + black)
  line((0.00pt, 71.76pt), (-62.15pt, -35.88pt), stroke: 0.7pt + black)
  line((0.00pt, 71.76pt), (-62.15pt, 35.88pt), stroke: 0.7pt + black)
  line((62.15pt, 35.88pt), (62.15pt, -35.88pt), stroke: 0.7pt + black)
  line((62.15pt, 35.88pt), (0.00pt, -71.76pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((62.15pt, 35.88pt), (-62.15pt, -35.88pt), stroke: 0.7pt + black)
  line((62.15pt, 35.88pt), (-62.15pt, 35.88pt), stroke: 0.7pt + black)
  line((62.15pt, -35.88pt), (0.00pt, -71.76pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((62.15pt, -35.88pt), (-62.15pt, -35.88pt), stroke: 0.7pt + black)
  line((62.15pt, -35.88pt), (-62.15pt, 35.88pt), stroke: 0.7pt + black)
  line((0.00pt, -71.76pt), (-62.15pt, -35.88pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, -71.76pt), (-62.15pt, 35.88pt), stroke: 0.7pt + black)
  content((39.53pt, 68.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250 dollars])
  content((31.07pt, 17.94pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210 dollars])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300 dollars])
  content((-23.62pt, 30.86pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200 dollars])
  content((-39.53pt, 68.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100 dollars])
  content((87.03pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220 dollars])
  content((31.07pt, -17.94pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120 dollars])
  content((-37.29pt, -21.53pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160 dollars])
  content((0.00pt, 41.88pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170 dollars])
  content((39.53pt, -68.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310 dollars])
  content((0.00pt, -41.88pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180 dollars])
  content((-37.29pt, 21.53pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330 dollars])
  content((-39.53pt, -68.46pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270 dollars])
  content((-23.62pt, -30.86pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150 dollars])
  circle((0.00pt, 71.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 71.76pt), text(size: 9pt, fill: black)[A])
  circle((62.15pt, 35.88pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((62.15pt, 35.88pt), text(size: 9pt, fill: black)[B])
  circle((62.15pt, -35.88pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((62.15pt, -35.88pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -71.76pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -71.76pt), text(size: 9pt, fill: black)[D])
  circle((-62.15pt, -35.88pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-62.15pt, -35.88pt), text(size: 9pt, fill: black)[E])
  circle((-62.15pt, 35.88pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-62.15pt, 35.88pt), text(size: 9pt, fill: black)[F])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. The edges, B D, C D, and D E are in dashed lines.", caption: [Finding the Fourth Vertex],
)


    So, mark #emph[B] as #math.equation(block: false, alt: "V sub 4")[$V_(4)$] for "visited 4th." Finally, compare the weights of the edges between #emph[B] and the remaining vertices adjacent to #emph[B]: \$160 and \$220 as shown. The lower amount is \$160, which is the edge between #emph[B] and #emph[E].


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[A])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[B])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[D])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[E])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[F])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. B is labeled V 4. The edges, B E and B C are in dashed lines.", caption: [Finding the Fifth Vertex],
)


    Now you can mark #emph[E] as #math.equation(block: false, alt: "V sub 5")[$V_(5)$] and mark the only remaining vertex, which is #emph[C], as #math.equation(block: false, alt: "V sub 6")[$V_(6)$]. This is shown. Make a note of the weight of the edge from #emph[E] to #emph[C], which is \$180, and from #emph[C] back to #emph[A], which is \$210.


    #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: (paint: black, thickness: 0.7pt, dash: "dashed"))
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[250])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[300])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((16.00pt, 9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[160])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[170])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[310])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((16.00pt, -9.24pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[330])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[270])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[150])
  circle((0.00pt, 42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[V 1])
  circle((36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[V 4])
  circle((36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[V 6])
  circle((0.00pt, -42.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[V 3])
  circle((-36.37pt, -21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[V 5])
  circle((-36.37pt, 21.00pt), radius: 10.50pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[V 2])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 250 dollars, 210 dollars, 300 dollars, 200 dollars, and 100 dollars. Edges from B leading to C, D, E, and F are labeled 220 dollars, 120 dollars, 160 dollars, and 170 dollars. Edges from C to D, E, and F are labeled 310 dollars, 180 dollars, and 330 dollars. Edges from D to E and F 270 dollars and 150 dollars. A is labeled V 1. F is labeled V 2. D is labeled V 3. B is labeled V 4. E is labeled V 5. C is labeled V 6. The edges, A C, and E C are in dashed lines.", caption: [Finding the Sixth Vertex],
)


    The Hamilton cycle we found is #emph[A] → #emph[F] → #emph[D] → #emph[B] → #emph[E] → #emph[C] → #emph[A]. The weight of the circuit is #math.equation(block: false, alt: "$ 100 plus $ 150 plus $ 120 plus $ 160 plus $ 180 plus $ 210 equals $ 920")[$"$" 100 + "$" 150 + "$" 120 + "$" 160 + "$" 180 + "$" 210 = "$" 920$]. This may or may not be the route with the lowest cost, but there is a good chance it is very close since the weights are most of the lowest weights on the graph and we found it in six steps instead of finding 120 different Hamilton cycles and calculating 60 weights. Let’s summarize the procedure that we used.


    #strong[Step 1:] Select the starting vertex and label #math.equation(block: false, alt: "V sub 1")[$V_(1)$] for "visited 1st." Identify the edge of lowest weight between #math.equation(block: false, alt: "V sub 1")[$V_(1)$] and the remaining vertices.


    #strong[Step 2:] Label the vertex at the end of the edge of lowest weight that you found in previous step as #math.equation(block: false, alt: "V sub n")[$V_(n)$] where the subscript n indicates the order the vertex is visited. Identify the edge of lowest weight between #math.equation(block: false, alt: "V sub n")[$V_(n)$] and the vertices that remain to be visited.


    #strong[Step 3:] If vertices remain that have not been visited, repeat Step 2. Otherwise, a Hamilton cycle of low weight is #math.equation(block: false, alt: "V sub 1 → V sub 2 → ⋯ → V sub n → V sub 1")[$V_(1) → V_(2) → ⋯ → V_(n) → V_(1)$].


    #examplebox("Example 4")[Using the Nearest Neighbor Method][
Suppose that the candidate for governor wants to hold rallies around the state but time before the election is very limited. They would like to leave their home in city #emph[A], visit cities #emph[B], #emph[C], #emph[D], #emph[E], and #emph[F] each once, and return home. The airfare between cities is not as important as the time of travel, which is indicated in . Use the nearest neighbor method to find a route with relatively low travel time. What is the total travel time of the route that you found?


        #figure(
  stdfig([#cetz.canvas({
  import cetz.draw: *
  line((0.00pt, 42.00pt), (36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, 42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, 21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (0.00pt, -42.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, -21.00pt), stroke: 0.7pt + black)
  line((0.00pt, -42.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  line((-36.37pt, -21.00pt), (-36.37pt, 21.00pt), stroke: 0.7pt + black)
  content((22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[120])
  content((10.18pt, 24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[140])
  content((0.00pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[85])
  content((-13.82pt, 18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[90])
  content((-22.48pt, 38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[180])
  content((44.61pt, 0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[100])
  content((10.18pt, -24.36pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[80])
  content((21.82pt, 12.60pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[95])
  content((-0.00pt, 15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[110])
  content((22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[220])
  content((-0.00pt, -15.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[200])
  content((21.82pt, -12.60pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[75])
  content((-22.48pt, -38.93pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[130])
  content((-13.82pt, -18.06pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[70])
  content((-44.61pt, -0.00pt), frame: "rect", fill: white, stroke: none, padding: 1pt, text(size: 8pt)[210])
  circle((0.00pt, 42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, 42.00pt), text(size: 9pt, fill: black)[A])
  circle((36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, 21.00pt), text(size: 9pt, fill: black)[B])
  circle((36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((36.37pt, -21.00pt), text(size: 9pt, fill: black)[C])
  circle((0.00pt, -42.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((0.00pt, -42.00pt), text(size: 9pt, fill: black)[D])
  circle((-36.37pt, -21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, -21.00pt), text(size: 9pt, fill: black)[E])
  circle((-36.37pt, 21.00pt), radius: 9.00pt, fill: white, stroke: 0.7pt + black)
  content((-36.37pt, 21.00pt), text(size: 9pt, fill: black)[F])
})]),
  alt: "A graph represents the airfares between six different cities. The graph has 6 vertices. The vertices are A, B, C, D, E, and F. Edges from A leading to B, C, D, E, and F are labeled 120 minutes, 140 minutes, 85 minutes, 90 minutes, and 180 minutes. Edges from B leading to C, D, E, and F are labeled 100 minutes, 80 minutes, 95 minutes, and 110 minutes. Edges from C to D, E, and F are labeled 220 minutes, 200 minutes, and 75 minutes. Edges from D to E and F are labeled 130 minutes and 70 minutes. An edge from E to F is labeled 210 minutes.", caption: [Travel Times between Cities #emph[A, B, C, D, E] and #emph[F]],
)


      
      #solutionbox[
#strong[Step 1:] Label vertex #emph[A] as #math.equation(block: false, alt: "V sub 1")[$V_(1)$]. The edge of lowest weight between #emph[A] and the remaining vertices is 85 min between #emph[A] and #emph[D].


        #strong[Step 2:] Label vertex #emph[D] as #math.equation(block: false, alt: "V sub 2")[$V_(2)$]. The edge of lowest weight between #emph[D] and the vertices that remain to be visited, #emph[B, C, E], and #emph[F], is 70 min between #emph[D] and #emph[F].


        #strong[Repeat Step 2:] Label vertex #emph[F] as #math.equation(block: false, alt: "V sub 3")[$V_(3)$]. The edge of lowest weight between #emph[F] and the vertices that remain to be visited, #emph[B, C,] and #emph[E], is 75 min between #emph[F] and #emph[C].


        #strong[Repeat Step 2:] Label vertex #emph[C] as #math.equation(block: false, alt: "V sub 4")[$V_(4)$]. The edge of lowest weight between #emph[C] and the vertices that remain to be visited, #emph[B] and #emph[E], is 100 min between #emph[C] and #emph[B].


        #strong[Repeat Step 2:] Label vertex #emph[B] as #math.equation(block: false, alt: "V sub 5")[$V_(5)$]. The only vertex that remains to be visited is #emph[E]. The weight of the edge between #emph[B] and #emph[E] is 95 min.


        #strong[Step 3:] A Hamilton cycle of low weight is #emph[A] → #emph[D] → #emph[F] → #emph[C] → #emph[B] → #emph[E] → #emph[A]. So, a route of relatively low travel time is #emph[A] to #emph[D] to #emph[F] to #emph[C] to #emph[B] to #emph[E] and back to #emph[A]. The total travel time of this route is: #math.equation(block: false, alt: "85 min plus 70 min plus 75 min plus 100 min plus 95 min plus 90 min equals 515 min or 8 hrs 35 min")[$85 #h(0.28em) min + 70 #h(0.28em) min + 75 #h(0.28em) min + 100 #h(0.28em) min + 95 #h(0.28em) min + 90 #h(0.28em) min = 515 #h(0.28em) min "or" #h(0.28em) 8 #h(0.28em) "hrs" #h(0.28em) 35 #h(0.28em) min$]
]
]


    
  
  
  
  
    
=== Key Terms


    - brute force algorithm
- greedy algorithm
- traveling salesperson problem (TSP)
- brute force method
- nearest neighbor method


  
  
    
=== Key Concepts


    - A brute force algorithm always finds the ideal solution but can be impractical whereas a greedy algorithm is efficient but usually does not lead to the ideal solution.
- A Hamilton cycle of lowest weight is a solution to the traveling salesperson problem.
- The brute force method finds a Hamilton cycle of lowest weight in a complete graph.
- The nearest neighbor method is a greedy algorithm that finds a Hamilton cycle of relatively low weight in a complete graph.


  
  
    
=== Formulas


    - In a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices, the number of distinct Hamilton cycles is #math.equation(block: false, alt: "open parenthesis n minus 1 close parenthesis !")[$( n − 1 ) !$].
- In a complete graph with #math.equation(block: false, alt: "n")[$n$] vertices, there are at most #math.equation(block: false, alt: "the fraction open parenthesis n minus 1 close parenthesis ! over 2")[$frac(( n − 1 ) !, 2)$] different weights of Hamilton cycles.