Welcome to the World of Networks!
Welcome to one of the most practical chapters in Further Mathematics! In this section, we are going to explore Networks. If you’ve ever used a GPS to find the quickest route home, wondered how delivery companies like Amazon plan their routes, or how the internet stays connected, you’ve already encountered the power of networks.
By the end of these notes, you’ll be able to speak the language of networks, find the most efficient ways to connect locations, and solve complex puzzles about traveling between different points. Don't worry if it seems like a lot of jargon at first—we’ll break it down piece by piece!
1. The Language of Networks
Before we can solve problems, we need to know what we are looking at. A Network (sometimes called a weighted graph) is simply a collection of points joined by lines, where the lines have numbers attached to them.
Key Terms to Master:
- Nodes (or Vertices): These are the "points" in your network. Think of them as cities on a map or computers in a room.
- Arcs (or Edges): These are the "lines" connecting the nodes. Think of them as the roads or cables.
- Weight: This is the number assigned to an arc. It represents a real-world value like distance, time, or cost.
Real-World Analogy: Imagine a map of your local area. The nodes are the shops, the arcs are the paths between them, and the weight is the number of minutes it takes to walk each path.
Quick Review Box:
- Node: A dot.
- Arc: A line.
- Weight: The "price" of that line.
2. Spanning Trees and Optimisation
Sometimes, we want to connect every node in a network using the minimum possible total weight. This is called a Minimum Spanning Tree (MST).
What is a Spanning Tree?
A tree is a graph where there are no "loops" (cycles) and everything is connected. A spanning tree is a tree that includes every single node in the network. Our goal in "optimisation" is usually to find the "cheapest" (minimum) way to do this.
Why is this useful?
Imagine you are a cable company. You want to provide fiber-optic broadband to 10 houses in a village. You want to use the least amount of cable possible while making sure every house is connected to the grid. This is an MST problem!
Key Takeaway:
A Spanning Tree connects all nodes with no cycles. To optimise it, we look for the set of arcs with the smallest total weight.
3. Route Inspection Problems
Have you ever seen a postman walking down every street in a neighborhood? They are solving a Route Inspection Problem (also known as the Chinese Postman Problem).
The Goal:
To find the shortest route that travels along every arc at least once and returns to the starting node.
How to Solve it (Step-by-Step):
- Check the Degrees: Look at each node and count how many arcs are connected to it. This is the degree.
- Identify Odd Nodes: If all nodes have an even degree, the network is Eulerian. You can travel every arc exactly once!
- Pair Up Odd Nodes: If there are nodes with odd degrees (there will always be an even number of them!), you must repeat the shortest paths between them to make them "even."
- Calculate Total Weight: Total Weight = (Sum of all arcs) + (Shortest repeated paths).
Common Mistake: Students often forget to look for the shortest path between odd nodes. If you have odd nodes A and B, the shortest path might not be a direct arc; it might go through node C!
4. The Travelling Salesperson Problem (TSP)
This is a classic! A salesperson needs to visit every node in a network and return to the start, but they want to keep the total distance as short as possible.
Upper Bounds and Lower Bounds
The TSP is actually very hard to solve perfectly for large networks. Instead, we find a range of values where the answer must lie.
1. Upper Bounds (Finding a "Good Enough" Route)
We use the Nearest Neighbour Algorithm.
Step 1: Start at a node.
Step 2: Go to the nearest unvisited node.
Step 3: Repeat until all nodes are visited, then return to the start.
Note: This gives us a maximum possible value for the best route. The "real" best route will be equal to or less than this.
2. Lower Bounds (Finding the "Floor")
To find the lower bound, we use the Deleted Node Method:
Step 1: Delete one node and all arcs connected to it.
Step 2: Find the Minimum Spanning Tree (MST) for the remaining nodes.
Step 3: Add the weights of the two shortest arcs that were connected to the deleted node.
Note: The "real" best route will be equal to or greater than this value.
Memory Aid:
- Upper Bound: Think of it as a "ceiling." We know the answer isn't worse than this.
- Lower Bound: Think of it as a "floor." We know the answer can't be better than this.
5. Evaluating and Refining Models
In Further Maths, we don't just "do the sums"; we think about whether the math makes sense in the real world.
Modifying the Model:
Don't worry if this seems tricky at first; it's mostly about using common sense! When using networks to represent reality, we might need to change them because:
- One-way streets: Arcs might only work in one direction (directed arcs).
- Traffic/Roadworks: The weights (time) might change depending on the time of day.
- Practicality: The shortest mathematical route might involve a turn that a large delivery lorry can't make.
Did you know? Refinement is a cycle. You create a model, see if it works, find the flaws, and then update the weights or arcs to make it more accurate.
Section Summary:
DB1: Nodes are dots, Arcs are lines, Weight is the value.
DB2: Spanning trees connect everyone without loops.
DB3: Route inspection covers every arc (Postman).
DB4: TSP covers every node (Salesperson). Use Nearest Neighbour for Upper Bound and Deleted Node for Lower Bound.
DB5: Always check if your network model matches real-life restrictions.