6.8: Exercise
- Page ID
- 38094
\( \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}}\)
\( \newcommand{\vectorA}[1]{\vec{#1}} % arrow\)
\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}} % arrow\)
\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vectorC}[1]{\textbf{#1}} \)
\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)
\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)
\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)
\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)
\(\newcommand{\avec}{\mathbf a}\) \(\newcommand{\bvec}{\mathbf b}\) \(\newcommand{\cvec}{\mathbf c}\) \(\newcommand{\dvec}{\mathbf d}\) \(\newcommand{\dtil}{\widetilde{\mathbf d}}\) \(\newcommand{\evec}{\mathbf e}\) \(\newcommand{\fvec}{\mathbf f}\) \(\newcommand{\nvec}{\mathbf n}\) \(\newcommand{\pvec}{\mathbf p}\) \(\newcommand{\qvec}{\mathbf q}\) \(\newcommand{\svec}{\mathbf s}\) \(\newcommand{\tvec}{\mathbf t}\) \(\newcommand{\uvec}{\mathbf u}\) \(\newcommand{\vvec}{\mathbf v}\) \(\newcommand{\wvec}{\mathbf w}\) \(\newcommand{\xvec}{\mathbf x}\) \(\newcommand{\yvec}{\mathbf y}\) \(\newcommand{\zvec}{\mathbf z}\) \(\newcommand{\rvec}{\mathbf r}\) \(\newcommand{\mvec}{\mathbf m}\) \(\newcommand{\zerovec}{\mathbf 0}\) \(\newcommand{\onevec}{\mathbf 1}\) \(\newcommand{\real}{\mathbb R}\) \(\newcommand{\twovec}[2]{\left[\begin{array}{r}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\ctwovec}[2]{\left[\begin{array}{c}#1 \\ #2 \end{array}\right]}\) \(\newcommand{\threevec}[3]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\cthreevec}[3]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \end{array}\right]}\) \(\newcommand{\fourvec}[4]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\cfourvec}[4]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \end{array}\right]}\) \(\newcommand{\fivevec}[5]{\left[\begin{array}{r}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\cfivevec}[5]{\left[\begin{array}{c}#1 \\ #2 \\ #3 \\ #4 \\ #5 \\ \end{array}\right]}\) \(\newcommand{\mattwo}[4]{\left[\begin{array}{rr}#1 \amp #2 \\ #3 \amp #4 \\ \end{array}\right]}\) \(\newcommand{\laspan}[1]{\text{Span}\{#1\}}\) \(\newcommand{\bcal}{\cal B}\) \(\newcommand{\ccal}{\cal C}\) \(\newcommand{\scal}{\cal S}\) \(\newcommand{\wcal}{\cal W}\) \(\newcommand{\ecal}{\cal E}\) \(\newcommand{\coords}[2]{\left\{#1\right\}_{#2}}\) \(\newcommand{\gray}[1]{\color{gray}{#1}}\) \(\newcommand{\lgray}[1]{\color{lightgray}{#1}}\) \(\newcommand{\rank}{\operatorname{rank}}\) \(\newcommand{\row}{\text{Row}}\) \(\newcommand{\col}{\text{Col}}\) \(\renewcommand{\row}{\text{Row}}\) \(\newcommand{\nul}{\text{Nul}}\) \(\newcommand{\var}{\text{Var}}\) \(\newcommand{\corr}{\text{corr}}\) \(\newcommand{\len}[1]{\left|#1\right|}\) \(\newcommand{\bbar}{\overline{\bvec}}\) \(\newcommand{\bhat}{\widehat{\bvec}}\) \(\newcommand{\bperp}{\bvec^\perp}\) \(\newcommand{\xhat}{\widehat{\xvec}}\) \(\newcommand{\vhat}{\widehat{\vvec}}\) \(\newcommand{\uhat}{\widehat{\uvec}}\) \(\newcommand{\what}{\widehat{\wvec}}\) \(\newcommand{\Sighat}{\widehat{\Sigma}}\) \(\newcommand{\lt}{<}\) \(\newcommand{\gt}{>}\) \(\newcommand{\amp}{&}\) \(\definecolor{fillinmathshade}{gray}{0.9}\)Skills
1. To deliver mail in a particular neighborhood, the postal carrier needs to walk along each of the streets with houses (the dots). Create a graph with edges showing where the carrier must walk to deliver the mail.
2. Suppose that a town has 7 bridges as pictured below. Create a graph that could be used to determine if there is a path that crosses all bridges once.
3. The table below shows approximate driving times (in minutes, without traffic) between five cities in the Dallas area. Create a weighted graph representing this data.
\(\begin{array}{|l|l|l|l|l|}
\hline & \text { Plano } & \text { Mesquite } & \text { Arlington } & \text { Denton } \\
\hline \text { Fort Worth } & 54 & 52 & 19 & 42 \\
\hline \text { Plano } & & 38 & 53 & 41 \\
\hline \text { Mesquite } & & & 43 & 56 \\
\hline \text { Arlington } & & & & 50 \\
\hline
\end{array}\)
4. Shown in the table below are the one-way airfares between 5 cities[1]. Create a graph showing this data.
\(\begin{array}{|l|l|l|l|l|}
\hline & \text { Honolulu } & \text { London } & \text { Moscow } & \text { Cairo } \\
\hline \text { Seattle } & \$ 159 & \$ 370 & \$ 654 & \$ 684 \\
\hline \text { Honolulu } & & \$ 830 & \$ 854 & \$ 801 \\
\hline \text { London } & & & \$ 245 & \$ 323 \\
\hline \text { Moscow } & & & & \$ 329 \\
\hline
\end{array}\)
5. Find the degree of each vertex in the graph below.
6. Find the degree of each vertex in the graph below.
7. Which of these graphs are connected?
8. Which of these graphs are connected?
9. Travel times by rail for a segment of the Eurail system is shown below with travel times in hours and minutes[2]. Find path with shortest travel time from Bern to Berlin by applying Dijkstra’s algorithm.
10. Using the graph from the previous problem, find the path with shortest travel time from Paris to München.
11. Does each of these graphs have an Euler circuit? If so, find it.
12. Does each of these graphs have an Euler circuit? If so, find it.
13. Eulerize this graph using as few edge duplications as possible. Then, find an Euler circuit.
14. Eulerize this graph using as few edge duplications as possible. Then, find an Euler circuit.
15. The maintenance staff at an amusement park need to patrol the major walkways, shown in the graph below, collecting litter. Find an efficient patrol route by finding an Euler circuit. If necessary, eulerize the graph in an efficient way.
16. After a storm, the city crew inspects for trees or brush blocking the road. Find an efficient route for the neighborhood below by finding an Euler circuit. If necessary, eulerize the graph in an efficient way.
17. Does each of these graphs have at least one Hamiltonian circuit? If so, find one.
18. Does each of these graphs have at least one Hamiltonian circuit? If so, find one.
19. 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:
- Using Nearest Neighbor starting in Fort Worth
- Using Repeated Nearest Neighbor
- Using Sorted Edges
\(\begin{array}{|l|l|l|l|l|}
\hline & \text { Plano } & \text { Mesquite } & \text { Arlington } & \text { Denton } \\
\hline \text { Fort Worth } & 54 & 52 & 19 & 42 \\
\hline \text { Plano } & & 38 & 53 & 41 \\
\hline \text { Mesquite } & & & 43 & 56 \\
\hline \text { Arlington } & & & & 50 \\
\hline
\end{array}\)
20. A salesperson needs to travel from Seattle to Honolulu, London, Moscow, and Cairo. Use the table of flight costs from problem #4 to find a route for this person to follow:
- Using Nearest Neighbor starting in Seattle
- Using Repeated Nearest Neighbor
- Using Sorted Edges
21. 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:
- Using Nearest Neighbor starting at building A
- Using Repeated Nearest Neighbor
- Using Sorted Edges
22. A tourist wants to visit 7 cities in Israel. Driving distances, in kilometers, between the cities are shown below[3]. Find a route for the person to follow, returning to the starting city:
- Using Nearest Neighbor starting in Jerusalem
- Using Repeated Nearest Neighbor
- Using Sorted Edges
\(\begin{array}{|l|l|l|l|l|l|l|}
\hline & \text { Jerusalem } & \text { Tel Aviv } & \text { Haifa } & \text { Tiberias } & \text { Beer Sheba } & \text { Eilat } \\
\hline \text { Jerusalem } & \_ & & & & \\
\hline \text { Tel Aviv } & 58 & \_ & & & \\
\hline \text { Haifa } & 151 & 95 & \_ & & \\
\hline \text { Tiberias } & 152 & 134 & 69 & \_ & & \\
\hline \text { Beer Sheba } & 81 & 105 & 197 & 233 & \_ & \\
\hline \text { Eilat } & 309 & 346 & 438 & 405 & 241 & \_ \\
\hline \text { Nazareth } & 131 & 102 & 35 & 29 & 207 & 488 \\
\hline
\end{array}\)
23. Find a minimum cost spanning tree for the graph you created in problem #3
24. Find a minimum cost spanning tree for the graph you created in problem #22
25. Find a minimum cost spanning tree for the graph from problem #21
Concepts
26. Can a graph have one vertex with odd degree? If not, are there other values that are not possible? Why?
27. A complete graph is one in which there is an edge connecting every vertex to every other vertex. For what values of n does complete graph with n vertices have an Euler circuit? A Hamiltonian circuit?
28. Create a graph by drawing n vertices in a row, then another n vertices below those. Draw an edge from each vertex in the top row to every vertex in the bottom row. An example when n=3 is shown below. For what values of n will a graph created this way have an Euler circuit? A Hamiltonian circuit?
29. Eulerize this graph in the most efficient way possible, considering the weights of the edges.
30. Eulerize this graph in the most efficient way possible, considering the weights of the edges.
31. Eulerize this graph in the most efficient way possible, considering the weights of the edges.
32. Eulerize this graph in the most efficient way possible, considering the weights of the edges.
Explorations
33. Social networks such as Facebook and LinkedIn can be represented using graphs in which vertices represent people and edges are drawn between two vertices when those people are “friends.” The table below shows a friendship table, where an X shows that two people are friends.
34.
- Create a graph of this friendship table
- Find the shortest path from A to D. The length of this path is often called the “degrees of separation” of the two people.
- Extension: Split into groups. Each group will pick 10 or more movies, and look up their major actors (www.imdb.com is a good source). Create a graph with each actor as a vertex, and edges connecting two actors in the same movie (note the movie name on the edge). Find interesting paths between actors, and quiz the other groups to see if they can guess the connections.
35. A spell checker in a word processing program makes suggestions when it finds a word not in the dictionary. To determine what words to suggest, it tries to find similar words. One measure of word similarity is the Levenshtein distance, which measures the number of substitutions, additions, or deletions that are required to change one word into another. For example, the words spit and spot are a distance of 1 apart; changing spit to spot requires one substitution (i for o). Likewise, spit is distance 1 from pit since the change requires one deletion (the s). The word spite is also distance 1 from spit since it requires one addition (the e). The word soot is distance 2 from spit since two substitutions would be required.
- Create a graph using words as vertices, and edges connecting words with a Levenshtein distance of 1. Use the misspelled word “moke” as the center, and try to find at least 10 connected dictionary words. How might a spell checker use this graph?
- Improve the method from above by assigning a weight to each edge based on the likelihood of making the substitution, addition, or deletion. You can base the weights on any reasonable approach: proximity of keys on a keyboard, common language errors, etc. Use Dijkstra’s algorithm to find the length of the shortest path from each word to “moke”. How might a spell checker use these values?
36. The graph below contains two vertices of odd degree. To eulerize this graph, it is necessary to duplicate edges connecting those two vertices.
- Use Dijkstra’s algorithm to find the shortest path between the two vertices with odd degree. Does this produce the most efficient eulerization and solve the Chinese Postman Problem for this graph?
- Suppose a graph has \(n\) odd vertices. Using the approach from part a, how many shortest paths would need to be considered? Is this approach going to be efficient?
[1] Cheapest fares found when retrieved Sept 1, 2009 for travel Sept 22, 2009
[2] From www.eurail.com/eurail-railway-map
[3] From http://www.ddtravel-acc.com/Israel-c...s-distance.htm