Algorithms on graphs

Welcome to the World of Graph Algorithms!

In this chapter of Decision Mathematics 1 (D1), we are going to learn how to solve real-world problems using graphs (networks). Imagine you are an engineer trying to connect several towns with fiber-optic cables using the least amount of material, or a delivery driver looking for the absolute shortest route between two cities. These aren't just guessing games—we use specific, step-by-step rules called algorithms to find the perfect answer every time.

Don't worry if this seems a bit abstract at first. We will break everything down into simple steps, use analogies you already know, and point out the "traps" students often fall into. Let's get started!

1. Minimum Spanning Trees (The "Minimum Connector" Problem)

Imagine you have a group of islands that you want to connect with bridges. To save money, you want to use the minimum total length of bridge possible, but you must make sure every island is connected to the network. This is called a Minimum Spanning Tree (MST).

Key Terms to Know:
• Vertex (Node): A point on the graph (like a town or island).
• Edge (Arc): The line connecting two vertices.
• Weight: The number on the edge (representing distance, cost, or time).
• Tree: A connected graph with no cycles (no loops).
• Spanning Tree: A tree that connects all the vertices in the graph.

There are two main algorithms to find an MST: Kruskal’s and Prim’s.

Kruskal’s Algorithm

Kruskal’s is like being a bargain hunter. You always look for the cheapest individual "deal" (edge) available, as long as it doesn't create a loop.

Step-by-Step Process:
1. List all the edges in the graph in order of size (smallest to largest).
2. Start with the shortest edge in the whole graph; add it to your tree.
3. Move to the next shortest edge. Add it unless it completes a cycle (a closed loop). If it makes a loop, throw it away!
4. Repeat until all vertices are connected. For \(n\) vertices, you will need exactly \(n - 1\) edges.

Common Mistake to Avoid: Students often forget to check for cycles. Always ask yourself: "If I add this edge, can I travel in a circle?" If the answer is yes, do not add that edge!

Prim’s Algorithm

Prim’s is different because it "grows" like a tree from a single starting point. You always look for the nearest neighbor to your current network.

Step-by-Step Process (on a Graph):
1. Pick any vertex to start (usually given in the question).
2. Look at all the edges connecting your "started" vertices to "unstarted" vertices. Choose the shortest one.
3. Add that new vertex to your set. Now look at all edges connecting any of your connected vertices to new ones.
4. Repeat until every vertex is included.

Prim’s on a Distance Matrix:
In your exam, you will often be asked to perform Prim's using a table (matrix). This is a very common requirement in the Pearson Edexcel syllabus.
1. Choose a starting vertex and label it "1" above its column.
2. Cross out the row for that vertex.
3. Look at the numbers in the columns that have been labeled (e.g., column 1). Circle the smallest available value.
4. The vertex for that row is your next vertex. Label its column "2", cross out its row, and repeat.

Quick Review Box:
• Kruskal's: Start with the shortest edge anywhere. Order doesn't matter, but cycles are forbidden.
• Prim's: Start with a vertex. Grow the network from what you've already connected.

2. Dijkstra’s Algorithm (Shortest Path)

While an MST connects everyone for the lowest cost, Dijkstra’s Algorithm is used to find the shortest path from one specific starting point to another specific destination. Think of this as the logic behind your GPS or Google Maps.

The Working Box:
In the exam, you will see a "box" at each vertex. It looks like this:
\( [ \text{Order of labeling} \mid \text{Final Label} \mid \text{Working Values} ] \)

Step-by-Step Process:
1. Start: Give the start vertex the final label 0. The order of labeling is 1.
2. Update: Look at all vertices connected to the one you just made "permanent." Calculate the distance from the start to these neighbors. Write these in the "Working Values" section.
3. Select: Look at all the temporary working values on the entire graph. Pick the smallest one. This is now your new "Permanent" vertex.
4. Finalize: Assign it the next "Order of Labeling" and its "Final Label" (the distance).
5. Repeat: Continue until your destination vertex receives a final label.

Analogy: Imagine water flooding a maze from the start point. The "Final Label" is the time the water first reaches that specific junction.

How to find the actual path:
Once you have the final labels, work backwards from the destination. A vertex \(B\) is on the path from \(A\) if:
\( (\text{Final Label of } B) - (\text{Final Label of } A) = \text{Weight of Edge } AB \)

Common Mistake to Avoid: When choosing the next permanent vertex, you must look at all temporary labels on the whole graph, not just the ones next to your current vertex!

Summary and Key Takeaways

Did you know?
The "Minimum Connector" problem was first solved by scientists trying to design efficient electricity grids in the 1920s. Today, the same math is used by companies like Netflix to ensure data travels quickly to your screen!

Final Review:
• Use Kruskal's if you have a list of all edges and want to avoid loops.
• Use Prim's if you are starting from a specific node or using a matrix/table.
• Use Dijkstra's if you need the shortest route from Point A to Point B.
• Always show your working values in Dijkstra’s—even if you cross them out. The examiners need to see your "thinking" on the paper!

Don't worry if this seems tricky at first! The best way to master these is to practice drawing the graphs and filling in the tables. Once you get the rhythm of the steps, it becomes like a puzzle that you can solve perfectly every time.