Networks and Graphs

Network Terminology and Building Models

A network or graph consists of a set of vertices (or nodes) linked by edges (or arcs). When edges carry numerical values like distance, travel time, or laying cost, the network is weighted. If every edge permits travel in only one direction marked by an arrow, the graph is directed (a digraph); if movement is bidirectional, it is undirected.

An undirected graph is connected if you can find a route between every pair of vertices. If any vertex or group of vertices sits isolated, the graph is disconnected. A disconnected graph cannot possess a spanning tree because no set of edges can link all vertices together.

Movement across a network follows precise definitions:

• Walk: A sequence of alternating vertices and edges where both vertices and edges may be repeated (for example, stepping back and forth along the same road).
• Path: A walk in which no vertex is visited more than once.
• Cycle: A closed path that starts and finishes at the same vertex, with no other repeated vertices.
• Tree: A connected undirected graph with no cycles. A tree with $n$ vertices always contains exactly $n - 1$ edges.
• Spanning tree: A subgraph containing every vertex of the original graph that forms a tree.

The number of edges meeting at a vertex is called its degree. In a simple undirected graph, the degree of a vertex equals the sum of the entries in its row of the adjacency matrix. In a directed graph, we count the two directions separately: a vertex's out-degree is the number of arcs leaving it (its row total in the adjacency matrix) and its in-degree is the number of arcs arriving at it (its column total).

Building a Network from a Scenario

When translating a problem into a network model, determine three elements before drawing:

1. Identify the vertices: the distinct entities being joined, such as towns, servers, electrical substations, or project milestones.
2. Identify the edges: direct connections between pairs of vertices. Do not add an edge where traffic or signals must pass through an intermediary.
3. Identify the weights and units: specify whether weights represent distance in kilometres, transit time in minutes, or capital expenditure in euro.

Assumptions and Limitations

Every network model involves simplifications. In written questions, you are frequently asked to state an underlying assumption and a practical limitation:

• Road distances: we assume link transit times remain constant, whereas actual times fluctuate with weather and rush-hour congestion.
• Utility lines: we assume cables or water pipes run in straight lines at uniform cost per metre, ignoring varied ground terrain, bedrock, and land-access wayleaves.
• Project durations: we assume each activity duration is known with certainty, whereas real tasks face supplier delays and labour shortages.

Adjacency Matrices, Powers, and Graph Reconstruction

An adjacency matrix records the direct connections between vertices in an $n$-vertex graph using an $n \times n$ array.

Read an adjacency matrix row first, then column: the entry in row $i$, column $j$ records the edges going from vertex $i$ to vertex $j$.

• In an unweighted simple graph, the entry $a_{ij} = 1$ if an edge runs from $i$ to $j$, and $0$ if there is no direct link.
• In an undirected graph, $a_{ij} = a_{ji}$, so the matrix is symmetric across its main diagonal.
• In a directed graph, symmetry generally breaks down because a link from $i$ to $j$ does not guarantee a link from $j$ to $i$.
• When there are no self-loops, the leading diagonal contains only zeros.

Adjacency Matrix versus Distance Matrix

Candidates must distinguish between these two representations:

• An adjacency matrix records how many connections exist (using 0s and 1s, or small integers for parallel edges). Only adjacency matrices can be multiplied to count routes.
• A distance (weight) matrix records how long or costly each direct link is, placing a dash ($-$) or $\infty$ where no direct connection exists. You use distance matrices for Prim's tabular method or to read costs. You never multiply a distance matrix; its powers have no mathematical meaning.

Powers of an Adjacency Matrix

Multiplying an adjacency matrix $A$ by itself using standard row-by-column matrix multiplication yields a direct count of journeys:

For example, the diagonal entry $(A^2)_{ii}$ counts all walks of length 2 from vertex $i$ back to itself. In a simple undirected graph, this matches the degree of vertex $i$ because each incident edge provides an out-and-back walk ($i \to k \to i$).

If matrix $A$ records bus routes and matrix $B$ records rail connections across the same ordered hubs, the product entry $(AB)_{ij}$ gives the number of two-stage journeys from $i$ to $j$ made by taking a bus followed by a train.

Reconstructing a Graph from an Adjacency Matrix

To redraw a network from its matrix:

1. Read the dimensions: an $n \times n$ matrix contains $n$ vertices. Set down labelled nodes in alphabetical or numerical order.
2. Test for symmetry: if $a_{ij} = a_{ji}$ for all entries, the graph is undirected (draw plain lines). If not symmetric, the graph is directed (draw arrows pointing from row $i$ to column $j$).
3. Insert connections: an entry of 1 creates an edge. An entry of $k$ creates $k$ parallel edges. Non-zero diagonal entries $a_{ii}$ represent loops returning to the same vertex.

Minimum Spanning Trees: Kruskal's and Prim's Algorithms

A minimum spanning tree (MST) connects all $n$ vertices of a weighted, connected undirected graph using exactly $n - 1$ edges while producing the smallest possible sum of edge weights.

Kruskal's Algorithm

Kruskal's algorithm operates globally on the sorted edge list:

1. List every edge in the network in ascending order of weight.
2. Select the cheapest available edge.
3. Add the next cheapest edge, unless it creates a cycle with edges already accepted. If both endpoints already belong to the same connected component, reject the edge and write down the cycle it would close.
4. Stop immediately once exactly $n - 1$ edges have been accepted.

Prim's Algorithm

Prim's algorithm grows a single tree locally from a designated starting vertex:

1. Begin at the specified vertex (or choose any vertex if none is stated).
2. Look at all edges connecting any vertex already in the growing tree to any vertex outside the tree.
3. Pick the connecting edge with the lowest weight. Add that edge and its new vertex to the tree.
4. Repeat until all $n$ vertices belong to the tree.

Distance Table Method for Prim

When data appears as a distance matrix rather than a diagram:

1. Select the start vertex. Cross out its horizontal row and write label 1 above its vertical column.
2. Search all numbered columns for the smallest uncrossed numerical entry.
3. Circle this minimum number, identify its row vertex, write the next sequential number above that vertex's column, and cross out its row.
4. Search all numbered columns again for the lowest uncrossed weight. Repeat until every row is crossed out.

Comparing Kruskal and Prim

• Prim expands one unbroken tree. It never forms separate components, so it cannot create cycles and requires no cycle checks. It works well on dense networks and distance matrices.
• Kruskal builds separate fragments that gradually merge. It requires explicit cycle checks on each candidate edge. It is quick to execute by hand on sparse diagrams.
• Justification of correctness: Both are greedy algorithms that guarantee a globally optimal tree. At every step, the cheapest edge spanning the divide between vertices already connected and vertices not yet connected must belong to some minimum spanning tree; substituting any costlier edge across that divide would increase the total weight. Terminating after $n - 1$ non-cyclic edges guarantees a connected spanning tree of minimal weight.

Shortest Paths: Dijkstra's Algorithm

Dijkstra's algorithm determines the shortest path from a single source vertex to every other vertex in a weighted network. It requires all edge weights to be non-negative ($w \ge 0$).

Vertex Labelling Layout

Examiners award method marks for clear working boxes at each vertex. Draw a divided box beside each vertex:

• Order of permanent labelling (top left): 1, 2, 3, ...
• Permanent label (top right): the finalised shortest distance from the source.
• Temporary labels (bottom): working distance values, recorded left to right, with superseded numbers crossed out neatly rather than erased.

Algorithm Procedure

1. Set the source vertex permanent label to 0, mark its order as 1, and make all other initial labels empty or $\infty$.
2. From the vertex $u$ just made permanent, calculate tentative distances to each unvisited neighbour $v$:

If this candidate distance is smaller than the current temporary label at $v$, write the new value into $v$'s box and score a line through the old value.

1. Scan all temporary labels across the entire graph. Select the vertex with the lowest temporary value. Declare this value permanent, write it in the top right, and record the next order number in the top left.
2. Repeat steps 2 and 3 until the destination vertex receives its permanent label.

Finding the Route (Back-Tracking)

The permanent labels provide the minimum distance. To recover the sequence of vertices, trace backward from the destination $T$ to the source $S$. A preceding vertex $u$ sits on the shortest path to $v$ if and only if:

Dynamic Programming and Bellman's Principle of Optimality

Dynamic programming breaks multi-stage decision problems into simpler nested sub-problems. It is governed by Bellman's Principle of Optimality:

"An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision."

In plain English: every piece of a best route, from any point onwards, must itself be a best route from that point. Because dynamic programming evaluates the immediate cost plus the optimal remaining cost, it cannot be deceived by an attractive early step that leads into a costly dead end.

Dynamic Programming Terminology

• Stage ($n$): A step, time interval, or network layer in the decision process, numbered backward from the destination ($n = 1$ is the final transition into the target).
• State ($s$): The specific node, inventory level, or physical condition occupied at the start of a stage.
• Decision ($x$): The next state chosen from state $s$.
• Optimal policy: The complete schedule of optimal decisions from start to finish.
• Optimal value function ($f_n(s)$): The minimum (or maximum) cumulative return from state $s$ to project completion over $n$ remaining stages.

Algebraic Recurrence Relation

For finding a shortest route in a weighted directed acyclic network:

where $C(s, x)$ is the immediate cost of stepping from state $s$ to state $x$, and $f_{n-1}(x)$ is the optimal cumulative cost from state $x$ through all subsequent stages.

Required Contexts

The syllabus applies dynamic programming to four authentic problem types:

1. Routing: identifying least-cost paths across layered transit zones.
2. Stock control: choosing production or reorder quantities to satisfy varying monthly demands while minimising storage charges.
3. Allocation of resources: distributing limited funding, machinery, or staff across projects to maximise total return.
4. Equipment replacement: deciding whether to keep existing plant (paying higher repair costs) or trade it in for new machinery.

Project Scheduling: Networks, Critical Paths, and Floats

Project management uses activity-on-arc networks. Arrows represent activities with defined durations, while circular nodes represent milestone events marking the completion of incoming activities and the initiation of outgoing ones.

Drawing from a Precedence Table and Dummy Activities

1. Begin at a single start event (event 1 at time 0) and draw all activities with no predecessors leaving it.
2. An activity can only depart from an event once all its predecessors have arrived there.
3. End at a single finish event; any activity with no successor must terminate here.
4. Number events sequentially so that every arrow runs from a lower index to a higher index.

A dummy activity is drawn as a dotted arrow carrying zero duration and consuming no resources. It is required in two circumstances:

• Dependency logic: if activity D requires both B and C to finish, but activity E requires only C, activities B and C cannot run into the same event. Terminate C at its own event, launch E from there, and run a dotted dummy arrow from C's finish event to B's finish event where D starts.
• Unique identification: two parallel activities must not share the same start event and same end event, because activities are referenced by event pairs $(i, j)$. Insert a dummy to create a separate milestone.

Forward Pass and Backward Pass

• Earliest event time (EET): Set $\text{EET} = 0$ at the initial event. Moving forward to event $j$:

Take the maximum where arrows converge, because an event cannot occur until every preceding activity finishes.

• Latest event time (LET): Set $\text{LET} = \text{EET}$ at the final event. Moving backward to event $i$:

Take the minimum where multiple arrows depart backward, to protect every downstream deadline.

Activity Times and Floats

For an activity $(i \to j)$ of duration $d$:

• Earliest start $= \text{EET}_i$
• Earliest finish $= \text{EET}_i + d$
• Latest finish $= \text{LET}_j$
• Latest start $= \text{LET}_j - d$

Total float measures how long an activity can be delayed without delaying overall project completion:

Free float measures how long an activity can be delayed without delaying the earliest start of any immediate successor:

Critical Path and Sensitivity

The critical path is the longest path from start to finish; its length dictates the minimum total project duration. Activities on this path have zero total float. An activity whose endpoints satisfy $\text{EET} = \text{LET}$ is not automatically critical unless its duration matches $\text{LET}_j - \text{EET}_i$.

Sensitivity rule: If a non-critical activity is delayed, the overall project duration increases only by the amount by which that delay exceeds the activity's total float. When that happens, recalculate the event times, because the critical path may switch to that activity.

Algorithm Evaluation and Comparison

Higher Level examination questions regularly require students to justify their choice of algorithm or compare alternative methods.

Evaluating Shortest-Route Techniques

• Exhaustive listing (inspection): Checks every conceivable route. Works reliably on tiny toy graphs, but becomes impossible on real networks because route combinations grow factorially.
• Dijkstra's algorithm: Exceptionally fast. Solves the shortest path from the source to every other vertex simultaneously. However, its greedy logic requires non-negative edge weights. If any weight is negative (such as an incentive, toll refund, or environmental credit), making a label permanent prematurely can return an incorrect path.
• Dynamic programming (Bellman): Evaluates every state across ordered stages. It handles negative transition weights seamlessly and accommodates complex boundary constraints (such as machine capacity, warehouse limits, or fleet turnover cycles). It requires the network to be acyclic so stages cannot loop back on themselves.

Key terms

Adjacency matrix

A square matrix where the entry in row i and column j indicates the number of directed edges passing from vertex i to vertex j.

Walk

A sequence of alternating vertices and edges connecting an initial vertex to a terminal vertex, in which vertices and edges may be repeated.

Path

A walk in which no vertex is visited more than once.

Cycle

A closed path starting and ending at the same vertex with no other vertices repeated.

Tree

A connected undirected graph that contains no cycles, containing exactly n - 1 edges for n vertices.

Spanning tree

A subgraph that contains every vertex of the original graph and forms a tree.

Minimum spanning tree

A spanning tree in a weighted undirected graph whose total edge weight is the minimum possible.

Greedy algorithm

An algorithm that makes the locally optimal choice at each step without reconsidering earlier choices.

Bellman's Principle of Optimality

The principle stating that an optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with respect to the state resulting from that first decision.

Stage

A distinct step, time period, or network layer in a dynamic programming sequence, conventionally numbered backward from the final objective.

State

The condition, location, or parameter value of a system at the beginning of a dynamic programming stage.

Optimal policy

The complete sequence of decisions across all stages that achieves the optimum overall payoff or minimum total cost.

Temporary label

An interim upper-bound distance assigned to a vertex in Dijkstra's algorithm, subject to reduction when a shorter path is uncovered.

Permanent label

A finalised, fixed numerical value in Dijkstra's algorithm representing the confirmed shortest distance from the source vertex.

Earliest event time

The earliest time a project milestone event can be reached, calculated during the forward pass by taking the maximum incoming completion time.

Latest event time

The latest time an event can take place without delaying overall project completion, calculated during the backward pass by taking the minimum outgoing requirement.

Critical path

The continuous path of activities from project start to finish with zero total float, which dictates the minimum duration needed to complete the project.

Total float

The amount of time an activity can be delayed from its earliest start without delaying project completion: LET(head) - EET(tail) - duration.

Free float

The amount of time an activity can be delayed without delaying the earliest start of any immediate successor: EET(head) - EET(tail) - duration.

Dummy activity

An activity of zero duration and zero resource consumption, drawn as a dotted arrow to preserve dependency logic or provide unique identification.