Weighted Graphs and Networks (VCE SSCE General Mathematics): Revision Notes
Weighted Graphs and Networks
What are weighted graphs?
In graph theory, edges represent connections between vertices. Sometimes we have additional numerical information about these connections. For example, if an edge represents a road between two towns, we might know the distance along that road or the time it takes to travel.
We can show this extra information by placing numbers next to the edges. These numbers are called weights, and graphs that include them are called weighted graphs.
A weighted graph is a graph where each edge has a number (weight) associated with it, providing additional information about the connection between vertices.
The diagram above shows a weighted graph representing towns (vertices) and roads connecting them (edges). The numbers on the edges show the distances along each road in kilometres.
In this example, the weights represent distances between towns:
- The distance from Croghon to Bartow is km
- The distance from Croghon to Melville is km
- The distance from Melville to Kenton is km
These numerical values give us practical information we can use to solve real-world problems.
Networks
A network is a special type of weighted graph. Networks are weighted graphs where the weights represent physical quantities that can be measured. These physical quantities include:
- Distance (measured in kilometres, metres, miles, etc.)
- Time (measured in minutes, hours, etc.)
- Cost (measured in dollars, pounds, etc.)
Key Distinction: The key difference between a weighted graph and a network is that networks must have weights that represent measurable, real-world quantities.
The example above showing towns and road distances is a network because the weights represent the physical quantity of distance.
Shortest path problems
When we know numerical information about the connections in a graph, we can solve practical problems about travelling through the network. These are called shortest path problems.
Depending on what the weights represent, we can find:
- The route with the shortest distance (if weights represent distance)
- The route with the shortest time (if weights represent time)
- The route with the lowest cost (if weights represent cost)
Finding the shortest path by inspection
For networks with only a few vertices, we can find the shortest path between two vertices using a method called inspection.
The Inspection Method:
This systematic approach involves three key steps:
- Listing all possible route options from the starting vertex to the ending vertex
- Adding up the weights for each route
- Comparing the totals to find the route with the smallest weight
Sometimes it's obvious that certain routes will be much longer than others, so you don't need to calculate every single possibility.
Worked example: Finding the shortest path
Worked Example: Finding the Shortest Path in a Network
Question: Find the shortest path from Bartow to Kenton in the network below.
Solution:
Step 1: List all possible routes from Bartow to Kenton
Looking at the network, we can identify these possible routes:
- Route 1: Bartow → Stratmoore → Melville → Osburn → Kenton (B–S–M–O–K)
- Route 2: Bartow → Stratmoore → Melville → Kenton (B–S–M–K)
- Route 3: Bartow → Stratmoore → Osburn → Kenton (B–S–O–K)
Step 2: Calculate the total distance for each route
Add the weights along each route:
Route 1: B–S–M–O–K
Route 2: B–S–M–K
Route 3: B–S–O–K
Step 3: Compare and select the shortest path
Comparing the three totals:
- Route 1: km
- Route 2: km
- Route 3: 27 km ✓ (shortest)
Answer: The shortest path from Bartow to Kenton is 27 km, using the route B–S–O–K (Bartow → Stratmoore → Osburn → Kenton).
Remember!
Key Points to Remember:
- Weighted graphs have numbers (weights) on their edges that provide extra information about the connections between vertices
- Networks are weighted graphs where the weights represent physical quantities like distance, time, or cost
- Shortest path problems involve finding the route with the minimum total weight between two vertices
- For small networks, use the inspection method: list all possible routes, add up the weights for each route, and choose the one with the smallest total
- Always clearly state your final answer, including the route and the total weight