2.4 Graph Theory & Network Models: Shortest Path, Minimal Spanning Tree & Maximum Flow

PE Industrial and Systems Exam

Track your progress as you read

Finished sections get a check mark.

1 Exam Overview, Strategy & Systems Foundations

1.1 PE Industrial Exam Format, Official Specification & Reference Handbook Strategy 1.2 System Analysis Tools, Process Definition, Requirements Engineering & QFD 1.3 Performance Measures: Output, Productivity, OEE, Cost & Environmental Sustainability 1.4 Process Types (Discrete, Continuous, Manufacturing, Service) & Value Analysis/Engineering

2 Optimization, Queueing, Simulation, Networks & Markov Chains

2.1 Linear Programming Formulation, Graphical Solutions & Sensitivity Analysis 2.2 Queueing Theory Models (M/M/1, M/M/s) & Little's Law Applications 2.3 Discrete-Event Simulation, Random Variates & Model Validation 2.4 Graph Theory & Network Models: Shortest Path, Minimal Spanning Tree & Maximum Flow 2.5 Markov Chains: Transition Matrices, Steady-State Probabilities & Absorbing States 2.6 Decision Trees, Expected Value & Bottleneck Analysis (Theory of Constraints)

3 Project Management & Planning

3.1 Project Scheduling with CPM and PERT: Critical Path, Float, Probability & Crashing 3.2 Project Planning & Control: Scope and WBS, Gantt Charts, Critical Chain (CCPM), Risk & Earned Value

4 Facility Layout, Space, Capacity & Material Handling

4.1 Systematic Layout Planning (SLP) & Activity Relationship (REL) Analysis 4.2 Workstation Design, Aisle Sizing & Space Requirements Planning 4.3 Capacity Analysis: Machine Requirements, Scrap Allowances & Personnel Requirements 4.4 Material Handling Equipment Selection, Unit Loads & Handling Principles

5 Site Location, Warehousing & Facility Economics

5.1 Facility Location Models: Center of Gravity & Minisum / Minimax Distance 5.2 Warehousing Systems, Storage Assignment & Order Picking Operations 5.3 Facility Life-Cycle Economics, Replacement Analysis & Rearrangement Costs

6 Demand Forecasting, Production Planning, MRP & JIT

6.1 Demand Forecasting Methods: Moving Averages, Exponential Smoothing & Error Metrics 6.2 Aggregate Planning Strategies & Master Production Scheduling (MPS) 6.3 Material Requirements Planning (MRP), Bill of Materials & Capacity Planning 6.4 Just-in-Time & Lean Production Planning: Pull Systems, Kanban Sizing, Heijunka & SMED

7 Inventory Systems, Scheduling, Logistics & Transportation Modes

7.1 Deterministic Inventory Control: Classical EOQ, EPQ & Quantity Discounts 7.2 Stochastic Inventory Management: Safety Stock, Continuous / Periodic Review & Newsvendor 7.3 Production Sequencing, Dispatching Rules & Johnson's Algorithm 7.4 Supply Chain Logistics, Transportation Simplex & Distribution Network Design 7.5 Transportation Modes, Freight Economics & the Transshipment Model

8 Engineering Economics, Break-Even Analysis & Costing Systems

8.1 Equivalence, Cash Flow Analysis & Discounted Cash Flow Metrics (PW, FW, EAC) 8.2 Rate of Return Analysis (IRR, Incremental IRR) & Benefit-Cost (B/C) Ratios 8.3 Asset Depreciation (MACRS, Straight-Line), Tax Effects & Replacement Decisions 8.4 Break-Even Analysis, Technical Capability Assessment & Costing Systems (Traditional, ABC & Standard Costs)

9 Methods Engineering, Work Measurement, Learning Curves, Line Balancing & Process Planning

9.1 Methods Analysis, Process Charting & Motion Study (Therbligs, 5S) 9.2 Worker–Machine (Man–Machine) Charts, Multiple Activity Analysis & Synchronous Servicing 9.3 Time Study Fundamentals, Performance Rating & Allowance Factors 9.4 Predetermined Motion Time Systems (PMTS, MTM, MOST) & Work Sampling 9.5 Learning Curves: Unit and Cumulative-Average Models, Learning Rates & Applications 9.6 Assembly Line Balancing, Precedence Constraints & Efficiency Heuristics 9.7 Manufacturing & Service Process Planning: Operation Selection, Sequencing, Route Sheets, Fixturing & Mistake Proofing

10 Ergonomics, Human Capacity, Occupational Safety & DART Rates

10.1 Anthropometry, Percentile Design, Workstation Ergonomics & Link Analysis 10.2 Industrial Biomechanics, the NIOSH Lifting Equation & Lifting Aids 10.3 Limits of Human Capacity & Risk-Factor Tools: Work Physiology, Strength, Range of Motion, Vision, RULA & Slip Resistance 10.4 Environmental Ergonomics (Noise, Heat, Illumination), Human-Machine Systems & OSHA Safety 10.5 Safety Codes, Standards & Voluntary Guidelines (OSHA, ANSI, NIOSH, MIL-STD) and DART Rate Calculations

11 Statistical Process Control & Process Capability

11.1 Statistical Process Control for Variables (X-bar/R and X-bar/s Charts) 11.2 Statistical Process Control for Attributes (p, np, c, and u Charts) 11.3 Process Capability Indices (Cp, Cpk, Cpm, Pp, Ppk) & Sigma Levels

12 Design of Experiments, Acceptance Sampling & Quality Systems

12.1 Design of Experiments: 2^k Factorials, ANOVA & Taguchi Robust Design 12.2 Acceptance Sampling: OC Curves, AQL, LTPD, AOQL, Z1.4/MIL-STD-105E & Dodge-Romig 12.3 Quality Systems (Deming, TQM, ISO 9000, Benchmarking), Root Cause Analysis & DMAIC

13 Reliability Engineering & Maintenance Systems

13.1 Reliability Modeling, Failure Rates (lambda) & Life Distributions (Exponential, Weibull) 13.2 System Reliability Architecture: Series, Parallel, k-out-of-n & Redundancy 13.3 Equipment Maintenance Engineering, Availability (A), MTBF/MTTR & RCM

2.4 Graph Theory & Network Models: Shortest Path, Minimal Spanning Tree & Maximum Flow

Key Takeaways Explain This Topic AI

A network is a set of nodes joined by arcs; directed arcs allow flow one way, and a spanning tree connects all n nodes with exactly n − 1 arcs and no cycles.

Dijkstra's algorithm finds shortest paths from a source by permanently labeling, at each step, the unlabeled node with the smallest tentative distance; it requires non-negative arc lengths.

Kruskal's algorithm builds a minimal spanning tree by adding the cheapest remaining arc that does not form a cycle until n − 1 arcs are chosen.

The max-flow min-cut theorem states that the maximum flow from source to sink equals the smallest total capacity of any cut separating them.

Transportation, transshipment, assignment, and CPM scheduling problems are all special network models, so the same node-and-arc thinking applies across the exam.

Last updated: October 2026

2.4 Graph Theory & Network Models

The specification names graph theory and networks among the modeling techniques. Network models are linear programs with a special structure, but they have fast hand-solution methods. That makes them good exam material: a few minutes of careful bookkeeping gives an exact answer.

1. Graph Theory Vocabulary

Term Meaning Industrial example
Node (vertex) A point in the network Plant, warehouse, workstation, intersection
Arc (edge) A connection between two nodes Road, conveyor, pipeline, data link
Directed arc Flow allowed one way only One-way aisle, pipeline with check valve
Path A sequence of arcs joining two nodes A route from plant to customer
Cycle A path that returns to its start node A loop in a conveyor network
Connected graph Every node can reach every other node A complete plant utility grid
Tree A connected graph with no cycles A branch power distribution

Spanning tree A tree that touches all n n n nodes; it has exactly n − 1 n - 1 n − 1 arcs The minimum set of cables linking all buildings

Many exam models are special cases of network flow. The transportation and assignment problems are bipartite networks, the transshipment problem adds intermediate nodes, and CPM finds the longest path through a project network.

The example network for the rest of this section has six nodes (S, A, B, C, D, T) and nine undirected arcs with these lengths (miles or costs):

Arc S–A S–B A–B A–C B–C B–D C–D C–T D–T
Length 4 2 1 5 8 10 2 6 3
2. Shortest Path: Dijkstra's Algorithm

Use: fastest route for a delivery truck or AGV, least-cost path through a supply network, or equipment replacement modeled as a path.

Procedure (non-negative arc lengths only):

Give the source a permanent label of 0 and every other node a tentative label of infinity.

From the node most recently made permanent, update each neighbor's tentative label to the smaller of its current label and (permanent label + arc length). Record the predecessor.

Make the node with the smallest tentative label permanent.

Repeat until the destination is permanent, then trace predecessors back to the source.

Worked example (shortest path S to T):

Step Node made permanent Label Updates made
1 S 0 A = 4 (via S), B = 2 (via S)
2 B 2 A = min(4, 2 + 1) = 3 (via B); C = 10; D = 12
3 A 3 C = min(10, 3 + 5) = 8 (via A)
4 C 8 D = min(12, 8 + 2) = 10 (via C); T = 14 (via C)
5 D 10 T = min(14, 10 + 3) = 13 (via D)
6 T 13 Done

Tracing back: T ← D ← C ← A ← B ← S. The shortest path is S–B–A–C–D–T with length 13 . The direct-looking route S–A–C–T has length 15, which shows why greedy choices made from the source are not enough.

Warning

Dijkstra's algorithm can fail with negative arc lengths, such as a cost network that includes a rebate. Those cases need the Bellman-Ford algorithm or an LP formulation.

3. Minimal Spanning Tree (MST)

Use: connect every node at minimum total arc length when anything that is connected can reach anything else. Examples are laying fiber or compressed-air lines to all buildings, or connecting all sensors in a plant.

Kruskal's algorithm: sort arcs from shortest to longest. Add each arc in order unless it creates a cycle. Stop when n − 1 n - 1 n − 1 arcs are chosen.

Arc (length) Decision Reason
A–B (1) Add No cycle
S–B (2) Add No cycle
C–D (2) Add No cycle
D–T (3) Add No cycle
S–A (4) Reject S, A, B are already connected
A–C (5) Add Joins {S, A, B} to {C, D, T}; 5 arcs = n − 1 n - 1 n − 1 , so stop

The MST uses arcs A–B, S–B, C–D, D–T, and A–C, for a total length of 13 . Prim's algorithm gives the same tree by growing from any node and always adding the cheapest arc leaving the current tree.

Note

The MST is not the same as the set of shortest paths. Here the MST and the S-to-T shortest path both total 13 by coincidence, but the MST must reach every node, while a shortest path only joins two nodes.

4. Maximum Flow and the Max-Flow Min-Cut Theorem

Use: the most material, vehicles, or data that can move from a source to a sink through arcs with limited capacity, such as conveyor throughput, pipeline capacity, or evacuation routes.

Directed capacities (units per hour):

Arc S→A S→B A→B A→C B→D D→C C→T D→T
Capacity 10 8 4 6 9 3 8 6

Augmenting-path method (Ford–Fulkerson): find any path from S to T with spare capacity on every arc, send the smallest spare capacity along it, update the residual capacities, and repeat until no path remains.

Path S→A→C→T: bottleneck min(10, 6, 8) = 6. Send 6.

Path S→B→D→T: bottleneck min(8, 9, 6) = 6. Send 6.

Path S→B→D→C→T: residuals are S→B 2, B→D 3, D→C 3, C→T 2, so the bottleneck is 2. Send 2.

Arcs C→T and D→T are now full, so no path reaches T. Maximum flow = 14.

Check with a cut. A cut is a set of arcs whose removal separates S from T; its capacity is the total capacity of the arcs crossing from the S side to the T side. The cut {C→T, D→T} has capacity 8 + 6 = 14 8 + 6 = 14 8 + 6 = 14 . Cutting the source arcs {S→A, S→B} would cost 18. The max-flow min-cut theorem says the maximum flow equals the minimum cut capacity, so 14 is optimal. The saturated arcs into T are the bottleneck; adding capacity anywhere else cannot raise throughput.

5. Choosing the Right Network Model

Question asked Model Hand method
Best route between two points Shortest path Dijkstra labels
Connect all points at least total length Minimal spanning tree Kruskal or Prim
Most throughput from source to sink Maximum flow Augmenting paths; verify with a cut
Least-cost shipping from supplies to demands Transportation or transshipment VAM and MODI, or LP
One-to-one pairing at least cost Assignment Hungarian method
Earliest project completion Longest path (CPM) Forward and backward pass