Networks

Welcome to the World of Networks!

Hello! Welcome to one of the most practical and visual chapters in Further Mathematics: Networks. This chapter is part of the Modelling with Algorithms section. You will learn how to turn real-life problems—like finding the quickest route home or managing water flow through pipes—into diagrams that we can solve using logical steps (algorithms).

Don’t worry if this seems a bit abstract at first. Think of a network as a map where we strip away the unnecessary details to focus only on connections and costs. Let’s get started!

1. The Language of Graphs

Before we can solve problems, we need to speak the language. In mathematics, a "graph" isn't a chart with an x-axis; it’s a collection of dots and lines.

Key Terms

• Node (or Vertex): The "dots" in the diagram. These usually represent places (like cities or computer servers).
• Arc (or Edge): The "lines" connecting the nodes. These represent the paths between them.
• Order (or Degree) of a Node: The number of arcs attached to that specific node.
• Tree: A connected graph with no cycles (loops). Think of it like a family tree—no way to go in a circle!
• Digraph: Short for "Directed Graph." Here, the arcs have arrows showing you can only travel in one direction.

Special Types of Graphs

• Simple Graph: No loops (an arc connecting a node to itself) and no multiple arcs between the same two nodes.
• Complete Graph: Every single node is connected to every other node.
• Connected Graph: You can get from any node to any other node by following the arcs.
• Bipartite Graph: The nodes are split into two sets, and arcs only connect nodes from different sets. Analogy: Imagine a list of "Workers" and a list of "Jobs." You only draw lines between a worker and a job, never between two workers.

The Incidence Matrix

Sometimes, drawing a graph is messy. An Incidence Matrix is a table that shows which nodes are connected by which arcs. It’s a way for a computer to "see" the graph without a picture.

Quick Takeaway: Nodes are the "where," Arcs are the "how," and a Tree is a simple path with no circles.

2. Weights and Networks

In the real world, not all paths are equal. Some roads are longer; some pipes are wider.

A Network is simply a graph where each arc has a weight (a number) assigned to it. These weights could represent distance, time, cost, or capacity.

Did you know? Your GPS uses weighted networks every time you ask for the "fastest route." The weights are the estimated travel times for each road!

3. Minimum Connector Problems

Imagine you are laying fiber-optic cables to connect five villages. You want everyone to be connected, but cable is expensive, so you want the minimum total length. This is a Minimum Spanning Tree (MST).

Kruskal’s Algorithm (The "Greedy" Way)

Kruskal’s is simple: always pick the cheapest option available!

1. Sort all arcs in the network from smallest weight to largest.
2. Pick the smallest arc and add it to your tree.
3. Pick the next smallest arc. Crucial Rule: Do not pick an arc if it completes a cycle (a closed loop).
4. Repeat until all nodes are connected.

Prim’s Algorithm (The "Growing" Way)

Prim’s builds the tree one node at a time, like a plant growing roots.

1. Start at any node (usually the one the question tells you).
2. Look at all arcs connected to the nodes you have already reached.
3. Pick the arc with the smallest weight that connects to a new node.
4. Repeat until every node is in the tree.

Memory Aid: Prim’s starts at a Point (node). Kruskal’s starts with the Kosts (weights) of the arcs.

Quick Takeaway: Both algorithms give you the same total minimum weight. Kruskal’s looks at the whole list of arcs; Prim’s grows out from a starting node.

4. Dijkstra’s Algorithm (Shortest Path)

This is used to find the shortest path from one specific starting node to a destination. Unlike MST, we only care about the distance from the start.

Step-by-Step Logic:

1. Give the start node a distance of 0 and all other nodes a distance of "infinity."
2. From your current node, update the distances to all neighbors. (New distance = Distance to current node + Arc weight).
3. If the new distance is smaller than the old one, write it down!
4. Once you’ve checked all neighbors, mark the current node as "visited." You won't go back to it.
5. Pick the unvisited node with the smallest temporary distance and make it your new current node.
6. Repeat until you reach the destination.

Common Mistake: Students often pick the arc with the smallest number. Remember, Dijkstra’s looks at the total distance from the start, not just the next step!

5. Algorithmic Complexity

In Further Maths (MEI), we care about how "hard" a computer has to work. This is called Complexity.

• Kruskal’s and Prim’s: These have quadratic complexity, written as \(O(n^2)\), where \(n\) is the number of edges.
• Dijkstra’s: This also has quadratic complexity, \(O(n^2)\), but it is a function of the number of vertices.

What does \(O(n^2)\) mean? If you double the size of the network (\(2n\)), the time it takes to solve will roughly quadruple (\(2^2 = 4\)).

6. Network Flows

Now, imagine arcs are pipes and the weights are capacities (the maximum amount of "stuff" like water or data that can flow through).

Sources and Sinks

• Source (S): Where the flow starts.
• Sink (T): Where the flow ends.
• Rule: For every other node, Flow In = Flow Out. (Nothing gets stuck in the middle!)

Cuts and Capacity

A Cut is a line that completely separates the Source from the Sink. The Capacity of a Cut is the sum of the capacities of all arcs crossing the cut from the S-side to the T-side.

Important: If an arc crosses back from the T-side to the S-side, we ignore its capacity (it's 0) when calculating the cut's value.

The Max Flow / Min Cut Theorem

This is a "Golden Rule" in networks: The maximum possible flow in a network is equal to the capacity of the minimum cut.

If you find a flow of 20 and a cut of 20, you have proven that 20 is the absolute maximum!

Quick Takeaway: Max flow is limited by the "bottlenecks" in the system (the minimum cut).

7. Solving Network Problems with Technology

In the real world, networks have thousands of nodes. We solve these by turning them into Linear Programming (LP) problems.

For a Shortest Path problem, we might set up equations where:

• The objective is to Minimise the total distance.
• The variables represent whether an arc is used (1) or not (0).
• The constraints ensure we enter and leave nodes correctly.

Don't worry about solving these by hand; the syllabus focuses on your ability to formulate the equations and interpret the output from software like Excel or a Simplex solver.

Final Encouragement

Network problems are like puzzles. Once you get the "rhythm" of Dijkstra’s or Prim’s, they become very satisfying to solve. Always draw your diagrams clearly, double-check your additions, and remember: algorithms are just recipes for math!