Welcome to Algorithms on Graphs!
In this chapter of Decision Mathematics 1 (D1), we are going to learn how to solve problems using "graphs" (which are just networks of dots and lines). Think of these as maps for delivery drivers, internet cables, or even social media connections.
We will focus on two main problems:
1. Minimum Spanning Trees: How to connect every point in a network using the least amount of "stuff" (like cable or road).
2. Shortest Path: How to get from point A to point B as quickly or cheaply as possible.
Don't worry if this seems a bit abstract at first! Once you see the step-by-step patterns, it becomes much like following a recipe.
1. Minimum Spanning Trees (MST)
Imagine you are laying fiber-optic cables to connect five villages. You want every village to be connected to the network, but cable is expensive, so you want to use the minimum total length. This is the Minimum Spanning Tree problem.
Key Terms to Know:
- Vertex (Node): A point on the graph (e.g., a village).
- Edge (Arc): The line connecting two vertices (e.g., the cable).
- Weight: The number assigned to an edge (e.g., its length or cost).
- Tree: A connected graph with no cycles (no loops).
- Spanning Tree: A tree that connects every vertex in the graph.
Kruskal's Algorithm
Kruskal's is the "edge-focused" algorithm. It is very simple: always pick the cheapest edge available, as long as it doesn't create a loop.
Step-by-Step:
1. List all the edges in the graph in order from smallest weight to largest weight.
2. Look at the smallest edge. If adding it doesn't create a cycle (a closed loop), select it.
3. Move to the next smallest edge and repeat.
4. Stop when all vertices are connected (for \(n\) vertices, you will have \(n-1\) edges).
Quick Tip: If an edge connects two points that are already reachable from each other through other selected edges, reject it because it creates a cycle!
Prim's Algorithm (on a Graph)
Prim's is the "vertex-focused" algorithm. It grows like a tree from a starting point.
Step-by-Step:
1. Pick any vertex to start (the question usually tells you which one).
2. Look at all the edges connected to the vertices you have already picked.
3. Choose the shortest edge that connects to a new vertex.
4. Repeat until every vertex is in your tree.
Analogy: Imagine a puddle of water starting at one village. The water always flows down the shortest available path to reach the next dry village.
Prim's Algorithm (on a Matrix)
Sometimes, the graph is given as a table of numbers (a distance matrix). Pearson Edexcel often asks you to perform Prim's directly on this table.
Step-by-Step:
1. Choose a starting vertex. Label its column "1" and cross out its row.
2. Look at the numbers in the columns you have labeled (the columns of vertices already in the tree).
3. Find the smallest number in those columns that isn't in a crossed-out row.
4. Circle that number. The row it is in is your new vertex.
5. Label the new vertex's column with the next number (2, then 3, etc.) and cross out its row.
6. Repeat until all rows are crossed out.
Common Mistake: Forgetting to look at all labeled columns. When you are looking for the next smallest number, you must check every column that has a number at the top!
Key Takeaway for MST:
Kruskal's involves sorting all edges first. Prim's involves building the tree one vertex at a time. Both will give you the same total minimum weight!2. Dijkstra's Algorithm (Shortest Path)
While an MST connects everyone, Dijkstra's algorithm finds the shortest way to get from one specific start to one specific finish. This is exactly how Google Maps or a car's Sat-Nav calculates your route.
How it works:
Each vertex gets a "label box." In D1, this box usually has three parts:
1. The Vertex Name.
2. The Order of Labeling (when it became "permanent").
3. The Final (Permanent) Label (the shortest distance from the start).
There is also space for Temporary Labels (distances we are currently testing).
Step-by-Step Process:
1. Start: Give the start vertex a permanent label of \(0\). Mark it as the 1st vertex labeled.
2. Update: Look at all vertices directly connected to the vertex you just made permanent.
3. Calculate: For each connected neighbor, add the weight of the edge to the permanent label of your current vertex. Write this in the neighbor's temporary label area.
4. Choose: Look at all temporary labels across the entire graph. Find the smallest one.
5. Make Permanent: Make that smallest temporary label permanent. Mark its order of labeling (2nd, 3rd, etc.).
6. Repeat: Go back to Step 2 using the vertex you just made permanent. Continue until your destination vertex has a permanent label.
Did you know? Dijkstra's algorithm is "greedy." It always picks the closest available option, trusting that it's the best step toward the final goal.
Finding the actual path:
Once you have the numbers, how do you know which roads to take? You work backwards from the destination!
The Rule: If a vertex \(B\) is connected to vertex \(A\), and:
\((\text{Permanent Label at } B) - (\text{Weight of Edge } AB) = (\text{Permanent Label at } A)\)
...then the edge \(AB\) is part of your shortest path!
Don't worry if this seems tricky at first: The most important thing is to be neat. If your "temporary labels" are messy, you might pick the wrong number for the next permanent label.
Quick Review Box:
Dijkstra's Algorithm- Start: Label \(0\).
- Working: Add edge weights to the current permanent label.
- Selection: Always pick the global minimum temporary label to make permanent next.
- Backtracking: Use the labels to find the route at the end.
3. Summary and Tips for Success
Common Mistakes to Avoid:
- In Kruskal's: Accidentally including an edge that creates a cycle. Always double-check if two points are already connected before adding a new edge.
- In Prim's (Matrix): Forgetting to cross out the row of the new vertex. This prevents you from choosing a vertex you've already visited.
- In Dijkstra's: Forgetting to update a temporary label. If you find a smaller temporary distance to a vertex later in the process, you must replace the old temporary value with the new, smaller one.
Memory Aids:
- Kruskal's Keeps edges in order (K for Kruskal and Keep sorting).
- Prim's Picks a starting vertex and grows (P for Prim's and Point of origin).
- Dijkstra is for Distance between two specific points.
Key Takeaway for the Chapter:
Algorithms on graphs are logical, step-by-step procedures. In the exam, the markers are looking for clear evidence of the steps. Always show your sorted list for Kruskal's, your labeling order for Prim's matrix, and all your temporary labels for Dijkstra's. Even if your final answer is slightly off, you can gain most of the marks by showing you followed the algorithm correctly!