• i. Maximum Flow: Push as much flow as possible from $s$ to $t$ through capacitated directed edges.
• ii. Push-Relabel: Instead of augmenting paths, maintain a preflow (vertices may hold excess) and heights $h$ with $h(u)\le h(v)+1$ for every residual edge $(u,v)$.
• iii. Flow Modeling: Most flow problems are modelling problems.
• iv. Minimum Cut: An $s$–$t$ cut is a set $S\ni s$, $t\notin S$; its capacity is the total capacity of edges leaving $S$.
• v. Global Minimum Cut: The cheapest way to split an undirected weighted graph into two non-empty parts, over all pairs.
• vi. Gomory-Hu Tree: For an undirected graph there is a weighted tree on the same vertices such that for every pair $u,v$ the minimum $u$–$v$ cut $\lambda (u,v)$ equals the minimum edge weight on the tree path, and remov
• vii. Min-Cost Flow: Edges have capacities and per-unit costs; send a required amount (or the maximum) from $s$ to $t$ as cheaply as possible, or more generally route given supplies and demands with lower bounds.
• viii. Assignment Problem: Assign $n$ workers to distinct jobs among $m\ge n$ minimising $\sum c_{i\sigma (i)}$:
• ix. Bipartite Matching: A matching is a set of edges without common endpoints.
• x. General Matching: Maximum matching in a non-bipartite graph.
• xi. Weighted General Matching: Maximum-weight matching in a general graph:
• xii. Matroid Intersection: Largest (or heaviest) set independent in two matroids $M_1,M_2$ on the same ground set.
• xiii. Stable Matching: Agents rank partners on the other side; a matching is stable if no pair $(p,a)$ prefer each other to their assigned partners (a blocking pair).