6.8 Exercise

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.

Map of a neighbourhood drawn as six square blocks in two rows of three, with small black squares marking the houses that line particular block edges. The top-left block has houses along its right side and its bottom side; the top-middle block has none; the top-right block has houses along its top, both sides and its bottom. The bottom-left block has houses along its top, its right side and its bottom; the bottom-middle and bottom-right blocks each have houses along their top side only.

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.

Map of a town in which a branching river, shaded, crosses the frame and divides the land into several regions, including a small island in the centre. Seven short black bars laid across the water mark the seven bridges.

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.

	Plano	Mesquite	Arlington	Denton
Fort Worth	54	52	19	42
Plano		38	53	41
Mesquite			43	56
Arlington				50

4. Shown in the table below are the one-way airfares between 5 cities[1]. Create a graph showing this data.

	Honolulu	London	Moscow	Cairo
Seattle	$$ 159$	$$ 370$	$$ 654$	$$ 684$
Honolulu		$$ 830$	$$ 854$	$$ 801$
London			$$ 245$	$$ 323$
Moscow				$$ 329$

5. Find the degree of each vertex in the graph below.

Graph with five vertices: three across the top (left, middle and right) plus one at the far lower left and one below the top-middle vertex. Six edges join top-left to top-middle, top-middle to top-right, top-left to the lower-middle vertex, top-middle to the lower-middle vertex, top-right to the lower-middle vertex, and the lower-left vertex to the lower-middle vertex.

6. Find the degree of each vertex in the graph below.

Graph with five vertices: two near the top, one at the left, one at the right and one at the bottom. Six edges join the top-left vertex to the left vertex, the top-right vertex to the left vertex, the top-right vertex to the right vertex, the left vertex to the right vertex, the left vertex to the bottom vertex, and the right vertex to the bottom vertex.

7. Which of these graphs are connected?

Three separate graphs side by side, each with five vertices set out as three across the top and two below. The first joins top-left to top-middle, top-middle to bottom-middle, bottom-left to bottom-middle and bottom-middle to top-right, and is connected. The second joins top-left to bottom-left and, separately, top-middle to bottom-middle, top-middle to top-right and bottom-middle to top-right, so it falls into two pieces. The third adds enough edges (top-left to bottom-left, top-left to top-middle, top-middle to top-right, top-middle to bottom-middle, bottom-left to bottom-middle and bottom-middle to top-right) to be connected.

8. Which of these graphs are connected?

Three separate graphs side by side, each with eight vertices set out as three along the top, two in the middle and three along the bottom. The first has a top path, a bottom path and an isolated middle edge, so it splits into three pieces. The second is connected: the two middle vertices are joined to each other and the right-hand middle vertex reaches the top-right, bottom-middle and bottom-right vertices while the left-hand middle vertex reaches the top-left. The third splits into two pieces, one containing the top-left, both middle, bottom-left and bottom-middle vertices and the other the top-middle, top-right and bottom-right vertices.

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.

Weighted graph of a segment of the Eurail network with seven city vertices: Amsterdam at the top, Berlin at the top right, Paris at the left, Frankfurt in the middle, Muenchen at the lower right, Bern below Frankfurt and Lyon at the bottom left. Eight edges carry travel times in hours and minutes: Paris to Amsterdam 1:25, Amsterdam to Berlin 6:10, Amsterdam to Frankfurt 4:00, Berlin to Muenchen 5:45, Frankfurt to Muenchen 3:10, Frankfurt to Bern 3:55, Bern to Lyon 3:50 and Lyon to Paris 1:55.

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.

Three separate graphs side by side. The first is a bow tie: two top vertices and two bottom vertices all joined to a single centre vertex, plus a top edge and a bottom edge, giving six edges and every vertex of even degree. The second has an apex above a middle row of three (left, centre, right) and a bottom row of two (centre and right), with ten edges; the apex and the middle-left vertex have odd degree. The third is a square with a centre vertex, in which the centre is joined to the top-left and bottom-right corners and by a double edge to the bottom-left corner, giving eight edges with the top-left and bottom-right corners of odd degree.

12. Does each of these graphs have an Euler circuit? If so, find it.

Three separate graphs side by side. The first is the complete graph on five vertices, a pentagon with all five diagonals drawn, ten edges in all and every vertex of degree 4. The second is a triangle with a smaller inverted triangle inside it, nine edges, every vertex of even degree. The third is a square with a fifth vertex inside near the top, joined to the two upper corners; six edges, and the two upper corners have odd degree.

13. Eulerize this graph using as few edge duplications as possible. Then, find an Euler circuit.

Rectangular grid graph of twelve unlabelled vertices in four rows of three, joined by all seventeen grid edges: two horizontal edges in each of the four rows and three vertical edges in each of the three columns. The six non-corner border vertices have odd degree.

14. Eulerize this graph using as few edge duplications as possible. Then, find an Euler circuit.

Grid of sixteen unlabelled vertices in four rows of four, joined by twenty-one of the twenty-four possible grid edges. Three grid edges are missing: the horizontal edge of the second row between columns two and three, the vertical edge of the first column between rows two and three, and the vertical edge of the third column between rows three and four.

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.

Map of an amusement park's major walkways drawn as smooth curving lines: an irregular closed outer loop with several interior paths crossing it, dividing the park into about six regions, plus a narrow rectangular spur on the far left and a short dead-end path leading off the bottom. No vertices or labels are marked.

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.

Street map of a neighbourhood drawn as a graph of eighteen vertices and twenty-two edges. Four vertices run across the top and four across the second row; the third row has two vertices at the left and two at the right; six vertices run along the bottom. Blocks are formed at the left by vertical streets in the first and second columns, while at the right a diagonal street runs down from the second row to the bottom row through a third-row vertex, and a second diagonal drops from the right-hand third-row vertex to the last vertex of the bottom row. Eight vertices have odd degree.

17. Does each of these graphs have at least one Hamiltonian circuit? If so, find one.

Three separate graphs side by side. The first is a bow tie: two top and two bottom vertices all joined to a centre vertex, plus a top edge and a bottom edge. The second is the complete bipartite graph with three vertices on top and three below, every top vertex joined to every bottom vertex, nine edges. The third has an apex, a middle row of three and a bottom row of three: the apex joins the outer two middle vertices, the middle row is joined left to centre to right, each outer middle vertex drops to the bottom vertex below it and also diagonally to the bottom-centre vertex, and the bottom row is joined left to centre to right.

18. Does each of these graphs have at least one Hamiltonian circuit? If so, find one.

Three separate graphs side by side. The first is a square inside a square: four outer corner vertices joined in a cycle, four inner vertices joined in a cycle, and a spoke from each outer corner to the inner vertex nearest it, twelve edges in all. The second is the complete bipartite graph with two vertices on top and three below, each top vertex joined to all three bottom vertices, six edges. The third has an apex, a middle row of three and a bottom row of two: nine edges join apex to middle-left and middle-right, along the middle row, from middle-left, middle-centre and middle-right down to the bottom-centre vertex, from middle-right to the bottom-right vertex, and along the bottom.

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

	Plano	Mesquite	Arlington	Denton
Fort Worth	54	52	19	42
Plano		38	53	41
Mesquite			43	56
Arlington				50

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

Weighted complete graph of five buildings: A at the top, B at the left, E at the right, C at the lower left and D at the lower right, with the cost in thousands of dollars to lay cable on each of the ten edges. A to B 5.9, A to C 5.1, A to D 4.7, A to E 4.4, B to C 6.0, B to D 4.3, B to E 5.2, C to D 5.6, C to E 4.0 and D to E 5.8.

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

	Jerusalem	Tel Aviv	Haifa	Tiberias	Beer Sheba	Eilat
Jerusalem	$_$
Tel Aviv	58	$_$
Haifa	151	95	$_$
Tiberias	152	134	69	$_$
Beer Sheba	81	105	197	233	$_$
Eilat	309	346	438	405	241	$_$
Nazareth	131	102	35	29	207	488

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?

Complete bipartite graph for n equal to 3: three vertices in a top row and three in a bottom row, with an edge from each top vertex to each of the three bottom vertices, nine edges in all and every vertex of degree 3.

29. Eulerize this graph in the most efficient way possible, considering the weights of the edges.

Weighted rectangular grid of twelve vertices in three rows of four, with seventeen edges. Every vertical edge has weight 1. In each of the three rows the horizontal edge between columns one and two has weight 2, the long edge between columns two and three has weight 3, and the edge between columns three and four has weight 2.

30. Eulerize this graph in the most efficient way possible, considering the weights of the edges.

Weighted rectangular grid of sixteen vertices in four rows of four, with twenty-four edges. Every vertical edge has weight 1. In each of the four rows the horizontal edge between columns one and two has weight 2, the long edge between columns two and three has weight 4, and the edge between columns three and four has weight 2.

31. Eulerize this graph in the most efficient way possible, considering the weights of the edges.

Weighted graph with five vertices: A at the top, B at the left, E at the right, C at the lower left and D at the lower right. Nine edges (every pair except C to E) carry the weights A to B 22, A to C 24, A to D 60, A to E 30, B to C 44, B to D 46, B to E 26, C to D 26 and D to E 28. C and E have odd degree.

32. Eulerize this graph in the most efficient way possible, considering the weights of the edges.

Weighted graph with five vertices: A at the top, E at the left, B at the right, D at the lower left and C at the lower right. Nine edges (every pair except B to C) carry the weights A to B 10, A to C 8, A to D 9, A to E 5, B to D 4, B to E 6, C to D 12, C to E 11 and D to E 13. B and C have odd degree.

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.

Friendship table with rows A to H and columns A to I; the cells on and below the diagonal are greyed out and an X marks each pair of friends. A is friends with B, C, F and G; B with C and E; C with E; D with E and I; E with G and I; F with H and I; G with H; and H with I.

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?

Weighted graph on a three-row by four-column grid of twelve vertices, with the seventeen grid edges plus two diagonals that cross in the middle. Top row horizontals: 4, then 7, then 5. Middle row: 7, then 5, then 2. Bottom row: 5, then 6, then 7. Vertical edges, reading top pair then bottom pair down each column: column one 2 and 3, column two 1 and 1, column three 3 and 2, column four 3 and 1. The diagonal from the top row of column two down to the bottom row of column three has weight 2, and the diagonal from the bottom row of column two up to the top row of column three has weight 3. Only the two middle-row end vertices, in columns one and four, have odd degree.

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

Adapted from Math in Society by David Lippman, hosted on LibreTexts (math.libretexts.org) and licensed under CC BY-SA 3.0. Changes were made. License: CC-BY-SA-3.0.