Graph Theory and Critical Path Analysis

A graph is a set of points joined by lines. That simple idea models road networks, precedence in a project, and much else — and critical path analysis turns it into a scheduling tool.

Graphs and terminology

A graph has vertices (nodes) joined by edges (arcs).

The handshaking lemma

$$\sum \text{degrees} = 2 \times (\text{number of edges})$$

Every edge has two ends, so it contributes 1 to the degree of each vertex it touches — 2 in total.

A graph has degrees $3, 3, 2, 2, 2$. How many edges?

$$\sum \text{degrees} = 12 \quad \Rightarrow \quad \text{edges} = \frac{12}{2} = 6$$

An immediate consequence: the number of odd-degree vertices is always even. The total of all degrees is even, so the odd ones must pair up.

Trees and spanning trees

A tree is a connected graph with no cycles. A tree with $n$ vertices has exactly

$$n - 1 \text{ edges}$$

Add one more edge and a cycle appears; remove one and it is no longer connected.

A spanning tree of a graph includes every vertex and enough edges to connect them, with no cycles. A graph with 6 vertices has spanning trees with 5 edges.

A minimum spanning tree has the smallest total weight. Two algorithms find one:

Kruskal's algorithm. Sort all edges by weight. Add them cheapest first, skipping any edge that would create a cycle, until $n-1$ edges are in place.

Prim's algorithm. Start at any vertex. Repeatedly add the cheapest edge joining the tree so far to a vertex not yet in it.

Activity networks

A project is a set of activities, each with a duration and a list of activities that must finish first.

Drawn as a network, activities run along edges (or sit in boxes) and the dependencies fix the order. A and B can start immediately; E must wait for both C and D.

Earliest and latest times

Forward pass — work left to right to find the earliest start (ES) and earliest finish (EF) of each activity. An activity cannot start until all its predecessors have finished, so take the maximum.

The project duration is 12.

Backward pass — work right to left to find the latest finish (LF) and latest start (LS) without delaying the project. Take the minimum of the successors' latest starts.

The critical path and float

$$\text{float} = \text{LS} - \text{ES} = \text{LF} - \text{EF}$$

the amount an activity can slip without delaying the project.

Activities with zero float are critical: any delay to one delays the whole project. They form the critical path:

$$B \to D \to E \qquad 4 + 5 + 3 = 12 \ \checkmark$$

which matches the project duration, as it must.