Welcome to the World of Networks!
Hello! In this chapter, we are going to explore Networks, which is a key part of the Modelling with Algorithms section. You might already use networks every day without realizing it—whenever you use a GPS for the quickest route home, or when a delivery company decides how to get a parcel to you, they are using the exact algorithms we are about to study. Don't worry if this seems a bit abstract at first; we’ll break it down into simple steps and relate it to real life!
1. The Language of Graphs and Networks
Before we can solve problems, we need to speak the language. A graph is just a collection of points and lines. When we add "weights" (like distances or costs) to those lines, it becomes a network.
Key Terms You Need to Know:
• Node (or Vertex): A point on the graph, usually representing a location (like a city).
• Arc (or Edge): A line connecting two nodes, representing a path or connection.
• Weight: A number assigned to an arc representing cost, time, or distance.
• Order (or Degree) of a Node: The number of arcs connected to that node.
• Simple Graph: A graph with no loops (an arc connecting a node to itself) and no multiple arcs between the same two nodes.
• Connected Graph: You can get from any node to any other node by following the arcs.
• Bipartite Graph: A graph where nodes are split into two sets, and arcs only connect nodes from different sets (think of "Workers" and "Jobs").
• Digraph: Short for "directed graph"—the arcs have arrows showing you can only travel in one direction.
Memory Aid: The "Social Media" Analogy
Imagine nodes are people and arcs are "Friendships." In a Simple Graph, you either are friends or you aren't. In a Digraph, it’s like "Following" someone on Instagram—you might follow them (an arrow points to them), but they might not follow you back!
Quick Review: An Incidence Matrix is just a table showing which nodes are connected. If Node A and Node B are connected by an arc with weight 5, you put a '5' in the row for A and column for B.
Key Takeaway: Graphs are the skeletons; Networks are the skeletons with data (weights) attached to them.
2. Minimum Connector Problems (MST)
Imagine you are laying fiber-optic cables to connect five villages. You want everyone to be connected to the internet, but cable is expensive, so you want the total length of the cable to be as short as possible. This is a Minimum Spanning Tree (MST) problem.
Kruskal’s Algorithm (Graphical Only)
This is the "Edge-First" approach. You don't care where you start!
Step 1: Sort all arcs from shortest to longest.
Step 2: Pick the shortest arc.
Step 3: Pick the next shortest arc. Important: If picking an arc creates a cycle (a closed loop), skip it!
Step 4: Repeat until every node is connected.
Prim’s Algorithm (Graphical or Tabular)
This is the "Node-First" approach. It grows like a tree from a starting point.
Step 1: Pick any starting node.
Step 2: Look at all arcs connected to the nodes you’ve already "captured." Pick the shortest one that connects to a new node.
Step 3: Repeat until all nodes are in your tree.
Did you know? Both Kruskal’s and Prim’s have quadratic complexity \(O(n^2)\). This means if you double the number of edges, the time the computer takes to solve it roughly quadruples!
Key Takeaway: Kruskal's = Pick the shortest edges anywhere. Prim's = Grow the tree from a starting point. Just remember: No Cycles!
3. Shortest Path: Dijkstra’s Algorithm
This is the "Google Maps" algorithm. It finds the shortest distance from one specific starting node to every other node in the network.
How to do it (Step-by-Step):
1. Label the start node with distance 0 and make it "permanent."
2. Update the "working values" of all nodes connected to your newest permanent node.
3. Look at all working values across the whole network. The node with the smallest working value becomes your next permanent node.
4. Repeat until your destination node is permanent.
Common Mistake: Students often only look at the nodes connected to the current one. You must look at the entire network to find the next smallest value to make permanent!
Key Takeaway: Dijkstra's is greedy—it always picks the closest "unvisited" node next. It also has quadratic complexity based on the number of vertices.
4. Critical Path Analysis (CPA)
This is used for project management—like building a house. Some jobs can't start until others finish. We use Activity-on-Arc diagrams where the arcs are the jobs and the nodes are "events" (points in time).
The Two Passes:
• Forward Pass: Calculates the Earliest Event Time (EET). You take the maximum value when multiple paths meet a node. (Think: "I can't start the roof until the walls AND the scaffolding are finished").
• Backward Pass: Calculates the Latest Event Time (LET). You take the minimum value when going backwards. (Think: "I must start this job by Tuesday, or the whole project will be late").
Understanding Float:
Float is the "wriggle room" an activity has. If an activity is on the Critical Path, it has zero float. If it’s late, the whole project is late!
\(Total Float = LET_{end} - EET_{start} - Duration\)
Key Takeaway: The Critical Path is the longest path through the network. It determines the minimum time needed to finish the project.
5. Network Flows
This models things like water in pipes or traffic on roads. You have a Source (S) where stuff starts and a Sink (T) where it ends.
The Rules of Flow:
1. Capacity: The flow through an arc cannot exceed its capacity.
2. Conservation: For every node (except S and T), Flow In = Flow Out.
The Max-Flow Min-Cut Theorem:
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 the arcs it crosses (only counting those pointing from the S-side to the T-side).
Important Rule: The Maximum Flow in a network is equal to the capacity of the Minimum Cut.
Analogy: Imagine a series of pipes. The amount of water reaching your house is limited by the "bottleneck"—the thinnest section of pipe in the whole system. That bottleneck is your Minimum Cut!
Key Takeaway: To find the maximum flow, look for the "bottleneck" (Min-Cut). The flow into a junction must always match the flow out.
6. Modeling with Linear Programming (LP)
While we can solve these by hand, computers use Linear Programming for big networks. You define variables for each arc (e.g., let \(x_{AB}\) be the flow from A to B).
• For Shortest Path: You minimize the sum of (Distances \(\times\) Variables).
• For Max Flow: You maximize the total flow out of the Source, subject to capacity constraints.
Key Takeaway: Complex network problems can be translated into equations that software (like Excel Solver) can solve instantly!
Final Encouragement
Networks might feel like a lot of boxes and lines at first, but they are just logical puzzles. Practice drawing the diagrams—it's much easier to see the "Minimum Cut" or the "Critical Path" when your drawing is neat and clear! You've got this!