Algorithms on graphs

Welcome to Algorithms on Graphs!

In this chapter, we are going to explore some of the most useful tools in Decision Mathematics. If you’ve ever wondered how Google Maps finds the quickest route home or how companies design cable networks to use the least amount of wire, you’re about to find out!

Decision Mathematics is all about efficiency—finding the best way to do things while saving time, money, or materials. Don't worry if these algorithms look like a lot of steps at first; they are just logical "recipes" that we follow. Let’s get started!

1. The Basics: What is a Graph?

Before we jump into the algorithms, let's make sure we know the language. In Decision Maths, a graph isn't a curve on an x-y axis; it's a collection of dots and lines.

Key Terms:
• Vertices (or Nodes): The points/dots on the graph.
• Edges (or Arcs): The lines connecting the vertices.
• Weight: A number attached to an edge (representing distance, cost, or time).
• Network: A graph where every edge has a weight.
• Path: A sequence of edges where you don't visit the same vertex twice.
• Cycle: A path that starts and ends at the same vertex (a loop).
• Tree: A connected graph with no cycles.
• Spanning Tree: A tree that connects all the vertices in the graph.

Quick Review: Think of a tree like a family tree—no matter how far you go, you can't go in a circle and end up back where you started!

2. Minimum Spanning Trees (MST)

Imagine you are a telecommunications engineer. You need to connect 5 cities with fiber-optic cables. You want all cities to be connected to the network, but you want to use the minimum total length of cable possible. This is the Minimum Spanning Tree problem.

We use two main algorithms to solve this: Kruskal’s and Prim’s.

Kruskal’s Algorithm

This is the "greedy" algorithm. It simply looks for the shortest edges in the whole network, regardless of where they are.

Step-by-Step:
1. Sort all the edges in the network into ascending order of weight (smallest to largest).
2. Pick the shortest edge and add it to your MST.
3. Pick the next shortest edge. Add it only if it does not create a cycle (a closed loop).
4. Repeat until all vertices are connected. For \(n\) vertices, you will need exactly \(n-1\) edges.

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

Prim’s Algorithm (on a network)

Prim’s is like a "growing" algorithm. It starts at one vertex and spreads out like a vine to the nearest neighbors.

Step-by-Step:
1. Pick any starting vertex.
2. Look at all the edges connecting already chosen vertices to unchosen vertices.
3. Pick the edge with the smallest weight and add it.
4. Repeat until every vertex is in your tree.

Did you know? Unlike Kruskal's, Prim's algorithm naturally avoids cycles because you are always connecting a "new" vertex to your "old" group.

Prim’s Algorithm (using a Matrix)

Sometimes, the network is given as a table (distance matrix) rather than a drawing. The syllabus specifically requires you to know how to do this.

Step-by-Step:
1. Choose a starting vertex (usually the first row) and delete that row. Label the column of that vertex with a "1".
2. Look at all the numbers in the columns that have a label (like "1").
3. Find the smallest number in those columns. The row it is in tells you the next vertex to add.
4. Write down the edge and its weight. Delete the row for this new vertex and label its column with the next number (e.g., "2").
5. Repeat until all rows are deleted.

Key Takeaway: Kruskal's builds the tree in bits and pieces all over the map. Prim's builds one single tree that gets bigger and bigger.

3. Dijkstra’s Algorithm (Shortest Path)

Dijkstra’s algorithm is used to find the shortest path from a single start vertex to a destination vertex. It’s exactly how Sat-Navs work!

We use a special labeling system on the vertices. Each vertex gets a box with three parts:
1. Order of Labeling: When was this vertex made "permanent"?
2. Final (Permanent) Label: The actual shortest distance from the start.
3. Working Values: Temporary distances we update as we find better routes.

Step-by-Step:
1. Label the start vertex with permanent label 0 and order of labeling 1.
2. Update: For the vertex you just made permanent, look at all its connected neighbors. Calculate the distance to them (Distance of current node + edge weight).
3. Write this as a working value at the neighbor. If there’s already a working value there, only replace it if the new one is smaller.
4. Choose: Look at all working values across the whole graph. Pick the smallest one. This becomes the next permanent label.
5. Repeat until your destination vertex is made permanent.

Don't worry if this seems tricky at first! Just remember the golden rule: Never make a working value permanent until you have checked every other possible way to get there. The smallest working value in the entire graph is always the one you pick next.

Finding the Path: Once you finish, how do you know which road to take? Work backward from the end! A vertex is on the shortest path if:
\( (Value \ at \ Vertex \ B) - (Value \ at \ Vertex \ A) = Weight \ of \ Edge \ AB \)

Quick Review Box:
• Kruskal/Prim: Connects everyone for the lowest total cost.
• Dijkstra: Connects one point to another for the shortest single journey.

4. Summary of Key Skills

To succeed in this chapter, you should be able to:
• State the difference between a path and a cycle.
• Use Kruskal’s by sorting edges and avoiding cycles.
• Use Prim’s on a diagram by always picking the nearest "neighbor" to the existing tree.
• Use Prim’s on a matrix by labeling columns and deleting rows.
• Use Dijkstra’s to find the shortest path between two points using the "box" method.

Final Tip: When performing these algorithms in an exam, show every step! Even if you get the final answer right, marks are often given for the list of edges in order (Kruskal) or the working values in the boxes (Dijkstra).