Network Problems (HSC SSCE Mathematics Standard): Revision Notes
Network Problems
The Königsberg bridge problem
The historical town of Königsberg (now called Kaliningrad) was built on the river Pregel in what was once Prussia. The town's unique layout featured seven bridges that connected two islands with the north and south banks of the river. This arrangement led to a famous mathematical puzzle.
The Königsberg bridge problem became one of the most famous puzzles in mathematics during the 18th century. Despite countless attempts by the townspeople and visitors, no one could find a solution - leading many to wonder if a solution even existed.
The Königsberg bridge problem asked a simple but intriguing question: could you plan a route that crosses each of the seven bridges exactly once, starting and finishing at the same location?
Many people attempted to find such a route, but they all failed. Every attempt resulted in either missing a bridge completely or having to cross at least one bridge twice. The diagrams showing attempted routes demonstrate this difficulty.
Euler's solution
The problem became famous throughout 18th century Europe and caught the attention of Swiss mathematician Leonhard Euler. Rather than trying different walking routes, Euler approached the problem differently. He created a simplified diagram to represent the situation, showing the land areas as points (called vertices) and the bridges as lines (called edges) connecting them. This type of simplified diagram is now called a network diagram or graph.
Using this network representation, Euler analysed the mathematical properties of the graph. He focused on the degree of each vertex, which is the number of edges meeting at that vertex. In the Königsberg bridge graph, all four vertices have an odd degree:
-
Each land area has an odd number of bridges connected to it
Eulerian trails
Euler proved a fundamental principle about graphs: a graph where all vertices have odd degree cannot be traced without either lifting your pencil from the paper or retracing an edge. This type of continuous path through a graph is called an Eulerian trail.
Euler's Principle: A graph with all vertices of odd degree cannot be traced or drawn without lifting the pencil or going over the same edge more than once.
This is the key principle that solved the Königsberg bridge problem. Since all four vertices in the Königsberg graph have odd degree, it is mathematically impossible to cross all seven bridges exactly once.
Based on this principle, Euler definitively solved the Königsberg bridge problem. The answer was no - it is impossible to cross all seven bridges exactly once in a single walk. At least one bridge must either be missed or crossed more than once.
Exam Tip: Remember that if a graph has all vertices with odd degree, you cannot trace it in one continuous path without retracing an edge. This is a common exam question that tests your understanding of Eulerian trails.
Solving practical network problems
Network diagrams can model many real-world situations. When edges have numbers assigned to them (such as distances, times, or costs), we call these weighted graphs. The numbers on the edges are called weights.
Weighted graphs are particularly useful for:
- Calculating shortest routes between locations
- Determining travel times through networks
- Finding the most efficient paths in transport systems
- Modeling cost-effective connections in networks
Worked example: Forest tracks problem
Worked Example: Finding Paths in a Weighted Graph
A network diagram is used to model walking tracks in a forest. The diagram shows connections between:
- A suspension bridge ()
- A waterfall ()
- A very old tree ()
- A fern gully ()
- Gate 1 ()
- Gate 2 ()
The numbers on the edges represent walking times in minutes between locations.
Part a: Construct a table to represent the weighted graph
To create a table from a network diagram:
- Use each vertex as both a row heading and a column heading
- For each edge connecting two vertices, enter the weight in both corresponding cells (because you can travel in either direction)
- Use a dash (–) where there is no direct connection
The table for this network is:
| W | G1 | F | B | T | G2 | |
|---|---|---|---|---|---|---|
| W | – | – | – | |||
| G1 | – | – | – | |||
| F | – | – | – | |||
| B | – | – | ||||
| T | – | – | – | – | ||
| G2 | – | – | – |
Part b: How long does it take to walk from the bridge directly to the fern gully?
To find the time for a direct walk:
- Locate the edge connecting (bridge) and (fern gully)
- Read the weight on this edge
The edge has a weight of minutes.
Answer: It takes minutes to walk directly from the bridge to the fern gully.
Part c: How long does it take to walk from the old tree to the fern gully via the waterfall and the bridge?
To find the total time for a path through specific locations:
- Identify the complete path:
- Find the weight of each edge along the path:
- to : minutes
- to : minutes
- to : minutes
- Add all the edge weights together:
Answer: It takes minutes to walk from the old tree to the fern gully via the waterfall and the bridge.
Converting Between Representations
Tables and network diagrams are two different ways to represent the same information. Both show:
- Which vertices are connected
- The weights (distances, times, or costs) of those connections
You should be comfortable converting between both representations and using whichever format is most helpful for solving a particular problem.
Exam Tip: When calculating path lengths, make sure you follow the exact route specified in the question and add up all edges along that route. A common mistake is to confuse direct paths with paths through intermediate vertices.
Remember!
Key Points to Remember:
-
The Königsberg bridge problem led to the development of graph theory when Euler proved that the seven bridges could not all be crossed exactly once.
-
A graph where all vertices have odd degree cannot be traced in one continuous path without lifting your pencil or retracing an edge (Eulerian trail).
-
Tables and network diagrams are two different ways to represent the same information about connections and weights between vertices.
-
To find the total length (time, distance, or cost) of a path, add up the weights of all edges along that path.
-
Always check whether you need a direct path between two points or a path that goes through specific intermediate vertices.