Skip to main content
\(\require{cancel}\newcommand\degree[0]{^{\circ}} \newcommand\Ccancel[2][black]{\renewcommand\CancelColor{\color{#1}}\cancel{#2}} \newcommand{\alert}[1]{\boldsymbol{\color{magenta}{#1}}} \newcommand{\blert}[1]{\boldsymbol{\color{blue}{#1}}} \newcommand{\bluetext}[1]{\color{blue}{#1}} \delimitershortfall-1sp \newcommand\abs[1]{\left|#1\right|} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Section16.2Chapter 16 Exercises

SubsectionSection 16.1 Exercises

1. A company needs to deliver product to each of their 5 stores around the Dallas, TX area. Driving distances between the stores are shown below. Find a route for the driver to follow, returning to the distribution center in Fort Worth: (a) using the Nearest Neighbor algorithm starting in Fort Worth, and (b) using the Repeated Nearest Neighbor algorithm; (c) then implement the result from (b) beginning at Arlington.


2. Apply the repeated nearest neighbor algorithm to the graph below to find a Hamilton circuit. After you find the circuit, implement it starting at vertex C.


3. When installing fiber optics, some companies will install a sonet ring; a full loop of cable connecting multiple locations. This is used so that if any part of the cable is damaged it does not interrupt service, since there is a second connection to the hub. A company has 5 buildings. Costs (in thousands of dollars) to lay cables between pairs of buildings are shown below. Find the circuit that will minimize cost: (a) using Nearest Neighbor from building A, and (b) using Repeated Nearest Neighbor, then implemented beginning from building E.


SubsectionSection 16.2 Exercises

4. Use the Cheapest Link (or sorted-edges) Algorithm on problem 1 above.

5. Use the Cheapest Link (or sorted-edges) Algorithm on problem 2 above.

6. Use the Cheapest Link (or sorted-edges) Algorithm on problem 3 above.