Network and route modeling

1 The graph shows routes that are available to an international lorry driver. The solid arcs represent motorways and the broken arcs represent ferry crossings. \includegraphics[max width=\textwidth, alt={}, center]{dfe6db33-33d0-4dff-95f7-fbf097e3963e-2_668_1131_587_466}

1. Give a route from Milan to Chania involving exactly two ferry crossings. How many such routes are there?
2. Give a route from Milan to Chania involving exactly three ferry crossings. How many such routes are there?
3. Give a route from Milan to Chania using as many ferry crossings as possible, without repeating any arc.
   [0pt]
4. Give a route leaving Piraeus and finishing elsewhere which uses every arc once and only once.[3]

1 Bus routes connect towns A and B and towns A and C .
Train lines connect towns B and D, towns C and D, and towns A and C.
John represents this information in a graph with four nodes, one for each town, in which an arc is drawn for each connection, giving five arcs in all.

1. Draw John's graph.
2. Is John's graph simple? Justify your answer. Jamil represents the information in a graph with five nodes. He uses one node for each of towns A, B and D. Because in town C the bus station and train station are some distance apart, he uses a node labelled C (bus) and a node labelled C (train). Again there are 5 arcs, each representing a connection.
3. Draw Jamil's graph.
4. Is Jamil's graph a tree? Justify your answer.

3 The graph represents four towns together with (two-way) roads connecting them. \includegraphics[max width=\textwidth, alt={}, center]{8eba759f-38bc-4d14-ac65-9a0ee6c79741-4_191_286_319_886} A path is a set of connected arcs linking one vertex to another. A path contains no repeated vertex. \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) are paths.

1. There are six paths from \(\mathrm { T } _ { 1 }\). List them.
2. List the paths from \(\mathrm { T } _ { 4 }\).
3. How many paths are there altogether? For this question a route is defined to be a path in which the direction of the arcs is not relevant. Thus \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route. Similarly \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 2 }\) and \(\mathrm { T } _ { 2 } \rightarrow \mathrm {~T} _ { 3 } \rightarrow \mathrm {~T} _ { 1 }\) are the same route (but note that \(\mathrm { T } _ { 1 } \rightarrow \mathrm {~T} _ { 2 } \rightarrow \mathrm {~T} _ { 3 }\) is different).
4. How many routes are there altogether?

3 Traffic flows in and out of a junction of three roads as shown in the diagram. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_296_337_333_863} Assuming that no traffic leaves the junction by the same road as it entered, then the digraph shows traffic flows across the junction. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_362_511_852_776}

1. Redraw the digraph to show that it is planar.
2. Draw a digraph to show the traffic flow across the junction of 4 roads, assuming that no traffic leaves the junction by the same road as it entered. \includegraphics[max width=\textwidth, alt={}, center]{839adc96-1bea-44ef-917e-f03e396a3061-3_366_366_1512_854}
   (Note that the resulting digraph is also planar, but you are not required to show this.)
3. The digraphs showing flows across the junctions omit an important aspect in their modelling of the road junctions. What is it that they omit?

3 \includegraphics[max width=\textwidth, alt={}, center]{c2deec7d-0617-4eb0-a47e-5b42ba55b753-4_399_1331_255_367}

1. By listing the vertices passed through, in the order they are used, give an example for the graph above of:
   1. a walk from A to H that is not a trail,
   2. a trail from A to H that is not a path,
   3. a path from A to H that is not a cycle. The arcs are weighted to form a network. The arc weights are shown in the table, apart from the weight of arc AG. The arcs model a system of roads and the weights represent distances in km.

      	A	B	C	D	E	F	G	H
      A	-	3	-	8	-	-	\(x\)	-
      B	3	-	5	-	-	-	-	-
      C	-	5	-	4	3	-	-	-
      D	8	-	4	-	5	-	-	9
      E	-	-	3	5	-	7	6	-
      F	-	-	-	-	7	-	-	-
      G	\(x\)	-	-	-	6	-	-	2
      H	-	-	-	9	-	-	2	-

      The road modelled by arc AG is temporarily closed.
2. Use the matrix form of Prim's algorithm to find a minimum spanning tree, of total weight 30 km , that does not include arc AG. The road modelled by arc AG is now reopened.
3. 1. For what set of values of \(x\) could AG be included in a minimum spanning tree for the full network?
   2. Which arc from the minimum spanning tree in part (b) is not used when arc AG is included?