Determine whether the following networks are trees:
For each of the following networks, determine whether it is a tree. Explain your answers.
Determine whether the following are properties that are true for all tree networks:
Removing any edge will make a disconnected subnetwork.
All of its subnetworks are connected.
No vertex has a degree higher than 2.
The number of edges is always one less than the number of vertices.
Every vertex shares an edge with every other vertex.
There is a unique path from any vertex to any other.
Adding an extra edge between two vertices will make another tree network.
There is no path from any vertex back to itself through the network.
Determine whether following networks have a spanning tree:
Consider this network:
How many vertices and edges does the network have?
How many vertices and edges will a spanning tree have?
Which edge (or edges) could we remove to make a spanning tree?
Draw a spanning tree for the network shown:
Explain why the network shown does not have a spanning tree.
Consider the given network:
How many edges would you have to delete to create a spanning tree?
Consider the given network:
Which edge from A has the lowest weight?
Of all the edges not from A, which one has the highest weight?
Construct the minimal spanning tree.
Construct the minimal spanning tree for each weighted network below.
Consider the network shown:
What is the weight of a minimal spanning tree?
How many different minimal spanning trees are there for the network?
Consider the network shown:
What is the weight of a minimal spanning tree?
How many different minimal spanning trees are there for the network?
In a certain area, the council wanted to lay down new electric cables. The given graph displays the map of the area:
To minimise the cost of cables, the council wants to connect the houses in such a way that they minimise the cable length. Construct a graph that will minimise the cable length.
Water pipes need to be laid down in a new area that is undergoing construction. The given graph shows the suggested plan where the numbers represent the lengths of the pipes:
To minimise the cost, the council wants to minimise the total length of water pipes used. Construct a graph that would achieve this.
Carbon can be converted between its different forms (graphite, diamond, nanotubes, and graphene). There are six machines that can convert between these forms, and the cost of the machines is presented in this network:
A scientist wants to convert between all four forms of carbon. Which three machines should he buy?
An engineer wants to convert only between diamond and nanotubes. Can she convert between these two forms of carbon using the three machines from part (a)?
Should she buy these three machines, or buy only the diamond-nanotubes machine?
The following network shows six theme parks, and the cost of bus trips between them:
Consider the first subnetwork shown:
Is this subnetwork a tree?
Is it a spanning tree?
What is its weight?
Consider the second subnetwork shown:
Is this subnetwork a tree?
Is it a spanning tree?
What is its weight?
A Full Bus Pass lets you ride along as many bus routes as you like, and it costs \$19. When is it a good idea to buy a Full Bus Pass?
First subnetwork:
Second subnetwork:
In the future, humanity develops a teleportation network between different stars in the solar system, represented by the edges in this network. Each teleporter requires a different amount of megatonnes (\text{Mt}) of nuclear fuel to power it for one month, represented by the weights on the edges:
Earth wants all the stars in the network to be reachable, but they also want to minimise the amount of fuel required to maintain the network. Which connections should they maintain?
How much fuel will they save by maintaining only the connections in the minimal spanning tree?