Trees and Minimum Connector Problems Revision Notes for VCE SSCE General Mathematics

Trees and Minimum Connector Problems

Introduction to connector problems

In many practical situations, we need to connect multiple locations while minimizing the total cost of connections. Unlike finding the shortest path between two points, connector problems focus on minimizing the total length or cost of connections needed to link all points in a network.

A common real-world example is connecting several towns to a water supply system. Rather than connecting each town to every other town (which would be very expensive), we can minimize costs by connecting each town to the network only once. This creates an efficient distribution system without unnecessary duplicate connections.

infoNote

The key idea is to minimize both the number of connections and the total weight (cost, distance, or time) of those connections while ensuring all points remain linked together.

What is a tree?

A tree is a special type of connected graph with specific characteristics. It represents the simplest way to keep vertices connected without any redundant paths.

chatImportant

Definition: A tree is a connected graph that has no loops, multiple edges, or cycles.

Key properties of trees:

All vertices are connected
There are no closed loops or cycles
There is exactly one path between any two vertices
Adding any edge creates a cycle
Removing any edge disconnects the graph

Important relationship: If a tree has $n$ vertices, it will have exactly $n - 1$ edges.

For example, a tree with $7$ vertices must have exactly $6$ edges.

This tree structure shows how seven vertices (labeled $A$ through $G$ ) can be connected with exactly six edges, demonstrating the $n - 1$ relationship.

Spanning trees

Every connected graph contains at least one subgraph that forms a tree. When this tree connects all the vertices in the original graph, we call it a spanning tree.

chatImportant

Definition: A spanning tree is a tree that connects all of the vertices of a graph.

To create a spanning tree from a graph:

Keep all vertices from the original graph
Remove enough edges to eliminate all cycles
Ensure all vertices remain connected

If the original graph has $n$ vertices and $e$ edges, the spanning tree will have $n$ vertices and $n - 1$ edges. This means we need to remove $e - (n - 1)$ edges.

infoNote

Total weight: The total weight of a spanning tree is the sum of all the weights on the edges that make up the tree. Different spanning trees from the same graph can have different total weights.

Finding the weight of a spanning tree

Let's work through an example to understand how to find the total weight of a spanning tree.

lightbulbExample

Worked Example: Finding the Weight of a Spanning Tree

Problem: Draw one spanning tree for the following graph and calculate its weight.

Solution:

Step 1: Count the vertices and edges in the original graph.

There are $9$ vertices and $13$ edges in the graph.

Step 2: Determine how many edges the spanning tree needs.

Since there are $9$ vertices, the spanning tree must have $9 - 1 = 8 \text{ edges}$ .

Step 3: Calculate how many edges to remove.

We need to remove $13 - 8 = 5 \text{ edges}$ from the original graph.

Step 4: Choose which edges to remove.

We must remove edges carefully to ensure:

All vertices remain connected
No cycles remain
Exactly $8$ edges are kept

The diagram shows which edges are removed (shown as dashed lines) and which are kept (solid lines).

Step 5: Calculate the total weight.

Add the weights of all remaining edges:

$\text{Weight} = 5 + 2 + 1 + 4 + 5 + 2 + 3 + 4 = 26$

The total weight of this spanning tree is $26$ .

Note that this is just one possible spanning tree for this graph. Different choices of which edges to remove would give different spanning trees, possibly with different total weights.

Minimum spanning trees

Among all possible spanning trees for a connected graph, one or more will have the smallest total weight. This is called the minimum spanning tree.

chatImportant

Definition: The minimum spanning tree is the spanning tree with the smallest possible total weight.

Finding the minimum spanning tree is important in many practical applications because it represents the most economical way to connect all vertices in a network. For instance:

Minimum cost for laying cables between towns
Shortest total pipeline length for gas or water distribution
Least expensive road network connecting cities

To find the minimum spanning tree efficiently, we use an algorithm called Prim's algorithm.

Prim's algorithm

Prim's algorithm provides a systematic method for finding the minimum spanning tree. It builds the tree step by step, always choosing the smallest available edge that doesn't create a cycle.

infoNote

Prim's algorithm for finding a minimum spanning tree:

Step 1: Choose any vertex as your starting point. (Any vertex will work, the algorithm will produce the same minimum spanning tree.)

Step 2: Look at all edges connected to your starting vertex. Select the edge with the smallest weight. This edge and the vertex it connects to become the beginning of your minimum spanning tree.

Step 3: Now examine all edges connected to any of the vertices currently in your tree. Choose the edge with the smallest weight, but ignore any edges that would connect the tree back to itself (creating a cycle).

Step 4: Add this new edge and its connected vertex to your tree.

Step 5: Repeat steps 3 and 4 until all vertices in the graph are connected to your tree.

Important: If two edges have the same weight, you can choose either one - it won't affect the final minimum total weight.

Worked example using Prim's algorithm

lightbulbExample

Worked Example: Applying Prim's Algorithm

Problem: Apply Prim's algorithm to find the minimum spanning tree for the following graph. Write down the total weight of the minimum spanning tree.

Solution:

We'll apply Prim's algorithm step by step, showing the tree being built progressively.

Starting point: Begin with vertex $A$ .

Step 1: From vertex $A$ , the smallest weighted edge goes to $B$ with weight $2$ .

The first diagram shows edge $AB$ highlighted in red.

Step 2: Looking at vertices $A$ and $B$ , the smallest available edge is from $A$ to $D$ with weight $5$ .

The second diagram shows edges $AB$ and $AD$ highlighted in red.

Step 3: Looking at vertices $A$ , $B$ , and $D$ , the smallest available edge is from $D$ to $C$ with weight $3$ .

The third diagram shows edges $AB$ , $AD$ , and $DC$ highlighted in red.

Step 4: From vertices $A$ , $B$ , $D$ , and $C$ , the smallest available edge is from $C$ to $E$ with weight $5$ .

Step 5: From vertices $A$ , $B$ , $D$ , $C$ , and $E$ , the smallest available edge is from $E$ to $F$ with weight $2$ .

All vertices are now connected.

Calculate the total weight:

Add all the edge weights in the minimum spanning tree:

$\text{Total weight} = 2 + 5 + 3 + 5 + 2 = 17$

The minimum spanning tree has a total weight of $17$ .

Minimum connector problems

Minimum spanning trees solve real-world connector problems where we need to link multiple locations with the minimum total cost, distance, or time.

infoNote

The key difference from shortest path problems:

Shortest path problems find the minimum distance between two specific points
Connector problems find the minimum total distance to connect all points together

Common applications include:

Connecting towns to utilities (water, gas, electricity)
Laying telecommunications cables
Designing road networks
Creating pipeline distribution systems

Practical example: Water pipe distribution

lightbulbExample

Worked Example: Water Pipe Distribution Network

Problem: Water is to be piped from a water tank to seven outlets on a property. The distances (in metres) between the tank and outlets, and between outlets, are shown in the network below.

Find the minimum length of pipe needed to supply water to all outlets.

Solution:

Part (a): Determine where pipes should be placed.

The minimum length will be achieved by using Prim's algorithm to find the minimum spanning tree.

Starting point: The Tank is our starting vertex.

Step 1: From the Tank, the smallest edge has weight $2$ (to Outlet C).

Step 2: From Tank and Outlet C, the smallest available edge has weight $5$ (from Outlet C to Outlet D).

Step 3: Continue applying Prim's algorithm, always selecting the smallest edge that doesn't create a cycle.

The diagram shows the final minimum spanning tree with pipes highlighted in red.

Part (b): Calculate the total length.

Add the weights of all edges in the minimum spanning tree:

$\text{Total length} = 2 + 6 + 5 + 8 + 7 + 10 + 6 = 44 \text{ metres}$

The minimum length of water pipe required is $44$ metres.

infoNote

Exam tip: When solving connector problems, always:

Clearly identify the starting vertex
Show your working step by step
Check that all vertices are included
State your final answer with appropriate units

Remember!

bookmarkSummary

Key Points to Remember:

A tree is a connected graph with no loops, multiple edges, or cycles. If a tree has $n$ vertices, it always has exactly $n - 1$ edges.
A spanning tree connects all vertices of a graph using the minimum number of edges (one less than the number of vertices).
The minimum spanning tree has the smallest possible total weight among all spanning trees for a graph.
Prim's algorithm finds the minimum spanning tree by repeatedly adding the smallest available edge that doesn't create a cycle, starting from any vertex.
Connector problems use minimum spanning trees to minimize the total cost, distance, or time needed to connect all points in a network, such as connecting towns to utilities or laying pipelines.

Trees and Minimum Connector Problems (VCE SSCE General Mathematics): Revision Notes