Graph theory
Model relations, inspect connectivity, and compare searches, dependencies, routes, spanning trees, flows, and assignments. Check what an optimum actually proves.
Prerequisite: Arithmetic. No programming, calculus, or prior graph theory required. Eleven lessons and 22 illustrated exercises connect graph definitions to search and optimization. Ten interactive views retain comparisons, exact edge records, and complete traces. Constructed networks distinguish mathematical certificates from claims about actual reliability, travel, capacity, or human assignments.
Lessons
- 1
Choose what the vertices and edges mean
Represent a concrete question as a graph without confusing a drawing with the system.
- 2
Count connections and represent the graph
Use degrees, adjacency lists, and matrices to inspect the same relation.
- 3
Distinguish walks, paths, cycles, and edge tours
Check what may repeat before deciding whether a route satisfies a task.
- 4
Find components and vulnerable connections
Separate local degree, reachability, and robustness to a link failure.
- 5
Search by layers or by depth
Follow a queue to prove fewest-edge distances and compare it with depth-first exploration.
- 6
Order dependencies and detect deadlock in the model
Remove ready tasks to construct a topological order or expose a blocking cycle.
- 7
Find a minimum-cost route under explicit assumptions
Relax tentative distances and see why nonnegative weights justify Dijkstra's settled set.
- 8
Connect every vertex with minimum total tree cost
Build a minimum spanning tree while keeping it distinct from a shortest-path tree.
- 9
Bound throughput with flows and cuts
Respect capacities and conservation, then use a cut as an optimality certificate.
- 10
Assign compatible pairs without double booking
Find maximum-cardinality bipartite matchings and diagnose shared shortages.
- 11
Audit a network recommendation
Choose the right objective and certificate before treating an algorithm's answer as advice.