DP Mathematics: Applications and Interpretation Questionbank

Verify that $G$ satisfies the handshaking lemma.

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

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}$.

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$.

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.

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.

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

Describe how an improved lower bound might be found.

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.

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

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.

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

Using Prim’s algorithm starting at vertex F.

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

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

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

Using Prim’s algorithm starting at vertex A.

Sketch the tracks that are to be tarmacked.

Using Kruskal’s algorithm.

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$.

Write down the adjacency matrix for this graph.

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

Show the direct flights between the cities as a graph.

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

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

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.

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

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

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.

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.

Define a Hamiltonian cycle.

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

Draw the graph of G.

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

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

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

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

Write down the adjacency matrix of the graph.

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

Draw a graph to represent this map.

Define an Eulerian circuit.

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

List the degrees of each of the vertices.

an Eulerian trail.

Write down an Eulerian circuit in G starting at P.

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

an Eulerian circuit.

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

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

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

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

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.

Write down the adjacency matrix for G.

What is the total weight of the tree?

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.

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.

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.

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.

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.

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

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

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

Write down an Eulerian trail in G.

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

Calculate the total weight of the solution.

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

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

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

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.

State, with a reason, whether or not G has 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.

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

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.

(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.

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.

(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.

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).

Draw the weighted graph $H$.

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.

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

Starting at A , use the nearest neighbour algorithm to find an upper bound for the travelling salesman problem for $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$.

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$.

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