A sewer inspector needs to plan the shortest possible route through each of the connections between different locations. Determine an appropriate start point and an appropriate end point of the inspection route.

Note that the fact that each location is connected to itself does not correspond to a sewer that needs to be inspected.

Starting at $\text{D}$, use the nearest neighbour algorithm to find the upper bound for the installation cost of a computer network in the form of a Hamiltonian cycle.

Note: Although the graph is not complete, in this instance it is not necessary to form a table of least distances.

Find the lowest cost road system and state the cost of building it. Show clearly the steps of the algorithm.

What is the total weight of the tree?

The weights of the edges of a complete graph G are shown in the following table.

Starting at B, use Prim’s algorithm to find and draw a minimum spanning tree for G. Your solution should indicate the order in which the vertices are added. State the total weight of your tree.

Write down an Eulerian trail in G.

Calculate the total weight of the solution.

Use the nearest neighbour algorithm to find an upper bound for the cost of the trip.

Sketch the tracks that are to be tarmacked.

Name an algorithm that will allow Sameer to find the lowest cost road system.

By deleting $\text{D}$, use the deleted vertex algorithm to find the lower bound for the installation cost of the cycle.

Starting at A, use Prim’s algorithm to find and draw the minimum spanning tree for G.

Your solution should indicate clearly the way in which the tree is constructed.

Hence find the minimum installation cost for the cables that would allow all the buildings to be part of the computer network.

State why a path that forms a Hamiltonian cycle does not always form an Eulerian circuit.

By using Kruskal’s algorithm, find the minimum spanning tree for $S$, showing clearly the order in which edges are added.

Draw a graph to represent this map.

an Eulerian circuit.

an Eulerian trail.

Define an Eulerian circuit.

Explain why it is not possible to have a Hamiltonian cycle in G.

Show that the lower bound you have obtained is not the best possible for the solution to the travelling salesman problem for G.

Use Prim’s algorithm to draw a minimum spanning tree starting at M.

Find the total number of Hamiltonian cycles in G, starting at vertex A. Explain your answer.

Find the number of distinct walks of length 4 beginning and ending at A.

Use a suitable algorithm to show that the minimum time in which Mr José can get from A to E is 13 minutes.

Using your answer to part (b), find the number of different ways to travel from and return to city A in exactly 6 flights.

Find the number of walks of length 4 from E to F.

State what feature of G ensures that G does not have an Eulerian circuit.

State what feature of G ensures that G has an Eulerian trail.

In the context of graph theory, explain briefly what is meant by a circuit;

List the degrees of each of the vertices.

By first removing library C, use the deleted vertex algorithm, to find a lower bound for Mathilde’s minimum travelling distance.

Find with a reason, the value of $x$.

Using Prim’s algorithm starting at vertex F.

State the total minimum length of the tracks that have to be tarmacked.

State whether or not it is possible to travel from and return to city A in exactly 6 flights, having visited each of the other 5 cities exactly once. Justify your answer.

Find the values of $a$ and $b$.

The diagram below shows a weighted graph.

Use Prim’s algorithms to find a minimal spanning tree, starting at J. Draw the tree, and find its total weight.

The weights of the edges in a simple graph G are given in the following table.

Use Prim’s Algorithm, starting with vertex F, to find and draw the minimum spanning tree for G. Your solution should indicate the order in which the edges are introduced.

Draw the graph of G.

Define a Hamiltonian cycle.

In this part, marks will only be awarded if you show the correct application of the required algorithms, and show all your working.

In an offshore drilling site for a large oil company, the distances between the planned wells are given below in metres.

It is intended to construct a network of paths to connect the different wells in a way that minimises the sum of the distances between them.

Use Prim’s algorithm, starting at vertex 3, to find a network of paths of minimum total length that can span the whole site.

Write down an Eulerian circuit in G starting at P.

By deleting $W$, use the deleted vertex algorithm to find a lower bound for the length of a route that visits every shop, starting and finishing at $W$.

By deleting vertex A, use the deleted vertex algorithm to find a lower bound for the cost of the trip.

The graph $G$ has six vertices and an Eulerian circuit. Determine whether or not its complement $G^{\prime }$ can have an Eulerian circuit.

Verify that $G$ satisfies the handshaking lemma.

Apply Prim’s algorithm to the weighted graph given below to obtain the minimal spanning tree starting with the vertex A.

Find the weight of the minimal spanning tree.

Using Prim’s algorithm starting at vertex A.

Write down the adjacency matrix for G.

Draw the weighted graph $H$.

Show the direct flights between the cities as a graph.

If the total length of the minimal spanning tree is 14, find the value of $s$.

Using Kruskal’s algorithm.

Briefly explain the two differences in the application of Prim’s and Kruskal’s algorithms for finding a minimum spanning tree in a weighted connected graph.

In the context of graph theory, explain briefly what is meant by an Eulerian circuit.

Use Kruskal’s algorithm to find a minimum spanning tree for G, stating its total weight. Indicate clearly the order in which the edges are added.

(i)     Draw the graph ${\kappa }_4$ including the weights of all the edges.

(ii)     Use the nearest-neighbour algorithm, starting at vertex ${\text{A}}_1$, to find a Hamiltonian cycle.

(iii)     Hence, find an upper bound to the travelling salesman problem for this weighted graph.

By splitting the weight of the edge ${\text{A}}_i{\text{A}}_j$ into two parts or otherwise, show that all Hamiltonian cycles of ${\kappa }_n$ have the same total weight, equal to the answer found in (c)(ii).

Which pairs of distinct vertices have more than 15 walks of length 3 between them?

Hence, find a lower bound for the travelling salesman problem for G.

Give an upper bound for the travelling salesman problem for the graph above.

Find a minimum spanning tree for the subgraph obtained by deleting A from G.

By first deleting vertex A , use the deleted vertex algorithm together with Kruskal’s algorithm to find a lower bound for the travelling salesman problem for $G$.

Starting from $W$, use the nearest-neighbour algorithm to find a route which gives an upper bound for this problem and calculate its length.

Starting and finishing at B, find a solution to the Chinese postman problem for G.

State, giving a reason, whether $G$ contains an Eulerian circuit.

Use Dijkstra’s algorithm to find the shortest time to travel from $\text{C}$ to $\text{F}$, clearly showing how the algorithm has been applied.

Hence write down the shortest path from $\text{C}$ to $\text{F}$.

Show that $G$ cannot be redrawn as a planar graph.

(i)     Use the nearest-neighbour algorithm, starting at vertex ${\text{A}}_1$, to find a Hamiltonian cycle.

(ii)    Hence find and simplify an expression in $n$, for an upper bound to the travelling salesman problem for this weighted graph.

Write down the adjacency matrix of the graph.

Write down the adjacency matrix for this graph.

Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $G$.

A new road is constructed that allows Christine to travel from $\text{H}$ to $\text{A}$ in $t$ minutes. If Christine starts from home and uses this new road her minimum travel time to $\text{A}$ is reduced, but her minimum travel time to $\text{F}$ remains the same.

Find the possible values of $t$.

Hence, state, with a reason, what can be deduced about the values of $p$, $q$, $r$.

Starting at library D use the nearest-neighbour algorithm, to find an upper bound for Mathilde’s minimum travelling distance. Indicate clearly the order in which the edges are selected.

Find an example of a graph $H$, with five vertices, such that $H$ and its complement $H^{\prime }$ both have an Eulerian trail but neither has an Eulerian circuit. Draw $H$ and $H^{\prime }$ as your solution.

Find the minimum time it takes Mr José to patrol the resort if he has to walk along every road at least once, starting and ending at A. State clearly which roads need to be repeated.

Describe how an improved lower bound might be found.

Hence find a lower bound for the travelling time needed to visit all the oil rigs.

Consider the graph ${\kappa }_5$. Use the deleted vertex algorithm, with ${\text{A}}_5$ as the deleted vertex, to find a lower bound to the travelling salesman problem for this weighted graph.

Find the number of walks of length 5 from P to Q.

Musab starts and finishes from the village bus-stop at $\text{A}$. Determine the total distance Musab will need to walk.

Use Prim’s algorithm to find the weight of the minimum spanning tree of the subgraph of $G$ obtained by deleting $\text{A}$ and starting at $\text{B}$. List the order in which the edges are selected.

Instead of having to catch the bus to the village, Musab’s sister offers to drop him off at any junction and pick him up at any other junction of his choice.

Explain which junctions Musab should choose as his starting and finishing points.

Nymphenburg Palace in Munich has extensive grounds with $9$ points of interest (stations) within them.

These nine points, along with the palace, are shown as the vertices in the graph below. The weights on the edges are the walking times in minutes between each of the stations and the total of all the weights is $105$ minutes.

Anders decides he would like to walk along all the paths shown beginning and ending at the Palace (vertex A).

Use the Chinese Postman algorithm, clearly showing all the stages, to find the shortest time to walk along all the paths.