Welcome to the World of Networks!
Hi there! Welcome to one of the most practical and "real-world" chapters in Further Mathematics. Have you ever wondered how Google Maps finds the fastest route to your friend's house, or how delivery companies like Amazon decide which roads their drivers should take to save fuel? That is exactly what Networks is all about!
In this chapter, we are going to learn how to turn real-life maps and connections into mathematical diagrams. Don't worry if it looks like a lot of lines and circles at first—we'll break it down step-by-step so you can master the logic behind it.
1. The Language of Networks (DB1)
Before we can solve complex problems, we need to speak the language. A network (also called a weighted graph) is just a collection of points joined by lines.
Key Terms to Know:
• Nodes (or Vertices): These are the "dots" or "points" in your network. Think of them as cities, houses, or computer servers.
• Arcs (or Edges): These are the "lines" connecting the nodes. Think of them as roads, cables, or flight paths.
• Weight: This is a number attached to an arc. It represents a "cost," such as distance (km), time (minutes), or money (£). If an arc between Node A and Node B has a weight of 5, it might mean it takes 5 minutes to travel between them.
Quick Review:
A network is just a graph where the lines have numbers (weights) on them. If you see a diagram with circles and lines, you're looking at a network!
2. Network Optimisation: Spanning Trees (DB2)
Imagine you are a cable company. You need to connect 5 houses so they all have internet. You don't need a road between every single house; you just need enough cable so that everyone is linked to the main hub. This is where Spanning Trees come in.
What is a Spanning Tree?
A tree is a graph with no cycles (no loops!). A spanning tree is a tree that connects every single node in the network. Our goal is usually to find the Minimum Spanning Tree (MST)—the one where the total weight of the arcs is as small as possible.
How to find the MST:
There are two main "recipes" (algorithms) you will use:
1. Kruskal’s Algorithm: You look at all the arcs in the whole network and always pick the shortest one available, as long as it doesn't create a closed loop.
2. Prim’s Algorithm: You start at one node and "grow" your tree by always picking the shortest arc that connects a node you’ve already visited to a node you haven't visited yet.
Analogy:
Kruskal’s is like a bargain hunter looking at a whole catalog of roads and picking the cheapest ones first. Prim’s is like a explorer starting at home and always taking the shortest path to a new, undiscovered land.
Key Takeaway:
To find a Minimum Spanning Tree, your final answer must connect all nodes using \(n - 1\) arcs (where \(n\) is the number of nodes) without ever forming a loop.
3. Route Inspection: The "Postman" Problem (DB3)
Now, imagine you are a postman. You have to walk down every single street in your neighborhood to deliver mail and then return to the sorting office. You want to do this while walking the shortest distance possible.
The Goal:
Traverse every arc at least once and return to the start.
The Logic:
If every node has an even degree (an even number of lines coming out of it), you can do this easily without repeating any roads! This is called an Eulerian circuit.
If there are odd nodes (nodes with an odd number of lines), you must repeat some roads. In the AQA syllabus, you will usually deal with networks that have two or four odd nodes.
Step-by-Step for 2 Odd Nodes:
1. Identify the two nodes with an odd degree.
2. Find the shortest path between these two nodes.
3. The total distance will be the sum of all weights in the network + the shortest path between those two odd nodes.
Common Mistake to Avoid:
Students often forget to add the "repeated" paths to the total weight of the network. Always start by calculating the "total weight of all arcs" first!
4. The Travelling Salesperson Problem (TSP) (DB4)
This sounds like the Postman problem, but it’s different! A salesperson doesn't need to walk every road; they just need to visit every city (node) once and return home.
Finding the absolute perfect route for TSP is actually very hard for computers to do. Instead, we find Upper Bounds and Lower Bounds to narrow down the answer.
Upper Bounds (The "Good Enough" Route)
An Upper Bound is a distance we know we can achieve. One common way to find it is the Nearest Neighbour Algorithm:
1. Start at a node.
2. Go to the nearest unvisited node.
3. Repeat until all nodes are visited.
4. Don't forget: You must add the distance to get back to the start!
Lower Bounds (The "Perfect World" Minimum)
A Lower Bound is a value that the best possible route cannot be shorter than. We find this using the Deleted Node Method:
1. Pick a node and "delete" it (ignore it and all arcs connected to it).
2. Find the Minimum Spanning Tree (MST) for the remaining nodes.
3. Find the two shortest arcs that were connected to the deleted node.
4. Lower Bound = Weight of MST + Two Shortest Arcs.
Did you know?
The Optimal Solution (the best possible route) will always sit somewhere between your Lower Bound and your Upper Bound. \(Lower Bound \le Optimal \le Upper Bound\).
5. Evaluating and Refining Models (DB5)
Math isn't always perfect. In the real world, a "weight" of 10 minutes might change if there is a traffic jam. Refining a model means adjusting your network to make it more realistic.
What might change?
• One-way streets: Arcs might only go in one direction (Directed Arcs).
• Road closures: An arc weight might become "infinite" if a road is blocked.
• Variable costs: Fuel prices or tolls might change the "weight" from distance to cost.
Quick Review Box:
• Spanning Tree: Connects all nodes with minimum cost (no loops).
• Route Inspection: Covers all arcs (The Postman).
• TSP: Visits all nodes and returns home (The Salesperson).
• Upper Bound: A route we found (usually using Nearest Neighbour).
• Lower Bound: A theoretical minimum (using Deleted Node + MST).
Don't worry if these algorithms feel repetitive at first. The more you practice tracing them on a diagram, the more natural they will feel! You've got this!