Apply Prim’s algorithm to the following network:
Starting at vertex A, which edge should be selected first?
Which edge should be selected second?
Which edge should be selected third?
What is the weight of the minimal spanning tree?
Apply Kruskal’s algorithm to the following network:
Which edge should be selected first?
Which edge should be selected second?
Which edge should be selected third?
What is the weight of the minimal spanning tree?
The following weighted network shows the number of stops on bus routes between major bus terminals:
Maintenance officers need to visit every bus terminal on Monday mornings.
Construct the minimum spanning tree.
What is the minimum number of stops that the officers would have to pass on their route?
The following weighted network shows possible connections (and associated costs, in millions of dollars) for connecting rural towns to a common cabled internet service:
To minimise the cost of connecting each town to the network, the minimal spanning tree must be found.
What is the minimum cost of connecting all of the towns together?
The direct flight routes between 5 major cities of the same country are shown in the given graph. Each edge is marked with the distance (in \text{km}) travelled on each route:
To optimise their investment, the operating airline wants to find the minimum spanning tree for the graph.
Construct the minimum spanning tree.
Using these flight routes, what is the minimum distance connecting these major cities?
The following weighted network shows the delay (in milliseconds) when sending coded messages between satellites used in navigation:
Technicians send these messages one at a time to ensure the satellites remain synchronised, and every satellite must be checked against at least one other satellite.
Construct the minimum spanning tree.
What is the minimum length of time it would take the technicians to perform the synchronisation check?
The water authority wants to lay water pipes along the roads in order to put a fire hydrant at every node on the network shown on the network. The numbers represent the length of the pipe that connects any two nodes.
To minimise the cost of the operation, the water authority wants to minimise the length of the pipes.
Construct a graph that will achieves this.
An airplane company wants to redesign their flight routes to make it cost efficient. The network displays the current flight routes:
In order for the flight routes to be efficient, the sum of the route distances needs to be minimised.
Construct the graph that will achieve this.
A large amusement park is trying to implement a new security system such that all security posts are connected by electric cabling. The network shows all possible connections and their respective lengths:
Since the project has a limited budget, the engineers have to minimise the length of cabling used.
Construct the graph that represents the least costly connections.
At the university, there is a new plan to connect all the campus buildings using underground fiber optic cables. The given network was suggested by the engineer:
The project accountant wanted to minimise the cost of the project. He realised that there are unnecessary cables that could be removed to minimise cable length.
Construct the network that represents the least cost.
Urban planners are trying to connect houses in a certain area.
The network represents all possible routes between houses in the area, and the distances between them.
The urban planners wish to create roads that are most distance efficient, and allow them to connect each house.
Construct the graph that is the most distance efficient.
In a certain area, new underground cables need to be laid to connect electric substations. The graph displays the current connection layout:
Since the project has a limited budget, the engineers have to design a connection layout that uses the minimum cable length.
Construct the graph that represents the connection layout with the least cost.
The rangers of a national park want to clear walking tracks to six landmarks in the area. The potential tracks between landmarks are shown in the following graph, along with the number of days required to clear each track for use.
To make a network of tracks in the shortest time, the rangers want to find a minimal spanning tree for the graph.
Construct a minimal spanning tree.
