In graph theory terms, state the definition of:
A tree
A spanning tree
A minimum spanning tree
A bridge
Determine whether the following statements about trees are true or false:
Adding one edge to any tree creates a new tree.
A tree has no Eulerian or Hamiltonian circuits.
If you remove any edge from a tree it creates a disconnected graph.
A tree has at least one Hamiltonian circuit, but not necessarily an Eulerian circuit.
Determine whether each of the following graphs is a tree. If it is not a tree, explain why.
Sarah has three children: Kate, Matt and Tom. Kate has four children: Lisa, Sandy, Amy and Robert. Matt has two sons: Joseph and Chris. Both Tom and Lisa have one child each: Barbara and Alex, respectively.
If the starting vertex represents Sarah, create a tree to represent the parent-child relationships in this family.
Bianca is writing a report and needs to create a table of contents. Her report consists of five chapters, each broken down into sections:
The first chapter is her introduction, so it has just one section.
Her second and third chapters both have three sections, while the fourth chapter has six sections.
The fifth and final chapter is the conclusion which again has only one section.
Create a tree that represents the structure of Bianca's table of contents.
Mitchell is tracing his family lineage back three generations:
His mother's name is Rebecca, and his father's name is Connor.
Rebecca's parents are Mabel and Patrick, and Connor's parents are Juliet and Mark.
Mitchell does not know Mabel's parents's names, but he knows that Patrick's parents are April and Todd.
On the other side, Mitchell knows that Juliet's parents are Daisy and Leonard, and Mark's dad is called Richard.
Mitchell does not know the name of Mark's mother, however.
If the initial vertex represents Mitchell, create a family tree of the last three generations from the information above. Make sure to include any ancestors that he doesn't know the name of using the word "Unknown".
Determine whether following networks have a spanning tree.
Construct a minimal spanning tree for each of the following weighted networks:
In a certain area, the council wanted to lay down new electric cables. The 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 pipe map was suggested:
To minimise the cost, the council wants to connect every house to water, minimising the total length of water pipes used. Construct a graph that would achieve this.
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, we want to find the minimal spanning tree.
How many edges will be required for the minimal spanning tree?
Construct the minimum spanning tree.
Find the minimum cost of connecting all of the towns to the service.
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 the investment put into these routes, the operating airline wants to find the minimum spanning tree for the graph.
How many edges will be a part of a spanning tree for this graph?
Construct the minimum spanning tree.
Using these flight routes, find the minimum distance connecting these major cities.
At a university, there is a new plan to connect all the campus buildings using underground fiber optic cables. The network given was suggested by the engineer:
The project accountant wants to minimise the cost of the project. He realises that there are unnecessary cables that can be removed to minimise cable length.
Construct the network that represents the least cost.
In a certain area, new underground cables need to be laid to connect electric substations. The given 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 minimum amount of cable.
An airplane company wants to redesign their flight routes to make it cost efficient. The given map displays the current flight routes:
In order for the flight routes to be efficient, each city needs to be connected and the sum of the route distances needs to be minimised.
Construct the graph that will achieve this.
The bus company decided to redesign its travel routes after some new roads were built. The given map shows the routes connecting the towns and the respective times (in minutes) taken to cover the route:
The bus company wants to connect all towns with the most time efficient route.
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 given map 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 connections using the least amount of cable.
Urban planners are trying to connect houses in a certain area. The given map 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.
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 given map. 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 the graph that will achieve this.
The rangers of a national park want to clear walking tracks to 6 landmarks in the area. The potential tracks between landmarks are shown in the given 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 the minimal spanning tree.
Find the minimum time taken to build a network of tracks that connect each landmark.
