Part 4 · 1 chapters · ~8 min

Graphs

Vertices and edges, directed and undirected graphs, degree and the handshake lemma, paths, cycles and connectivity, trees and their properties, DAGs and topological order, bipartite graphs, colouring and scheduling, Euler and Hamilton paths, and representing graphs in code.

Graphs in code

code

const deps = { 'payouts-api': ['ledger-api', 'queue', 'risk-api'], 'queue': ['rail-adapter'],
               'rail-adapter': ['ledger-api'], 'ledger-api': ['postgres'], 'risk-api': [], 'postgres': [] };

// topological order (Kahn): exists if and only if the graph has no cycle
function topo(g) {
  const indeg = Object.fromEntries(Object.keys(g).map(k => [k, 0]));
  for (const vs of Object.values(g)) for (const v of vs) indeg[v]++;
  const q = Object.keys(g).filter(k => indeg[k] === 0), out = [];
  while (q.length) { const u = q.shift(); out.push(u); for (const v of g[u]) if (--indeg[v] === 0) q.push(v); }
  if (out.length !== Object.keys(g).length) throw new Error('cycle');
  return out;          // reverse it for "build dependencies first"
}

fact	use
handshake lemma: Σ degrees = 2 × edges	sanity-check graph data; odd-degree vertices come in pairs
a tree on n vertices has n-1 edges	detect extra edges (cycles) in hierarchies
a graph is 2-colourable iff it has no odd cycle	bipartite checks: matching drivers to riders
graph colouring = scheduling without conflicts	exam timetables, register allocation in compilers

SYSTEMS ARE GRAPHS

vertices, edges, and what their shape tells you

swipe the figure sideways, or tap expand for full screen

1/4

vertices and edges

A graph is a set of vertices and edges. Services and their calls, packages and their imports, accounts and transfers: all graphs.

vertices + edgeseverywhere in systems