Graph Theory in Optimization: Flows and Matchings

Graphs as Models of the Real World

A graph is a mathematical abstraction of a network: vertices (nodes) and edges (connections). The Internet is a graph of routers. A social network is a graph of users. A transportation network is a graph of cities and roads. Many discrete optimization problems are graph problems. Three classical classes: flow problems (how to direct traffic in a network), matchings (how to assign tasks to executors), spanning trees (how to connect all nodes minimally). All of them are solved in polynomial time!

Maximum Flow

Formulation: a directed network G = (V, E) with capacities c(e) > 0 on each edge. Source s, sink t. Find the maximum flow from s to t.

Flow f: flow on edge (u,v) ≤ c(u,v), in each vertex (except s, t) the sum of incoming flows equals the sum of outgoing flows.

Ford-Fulkerson Theorem: max flow = min cut.

Cut (S, V∖S) with s ∈ S, t ∈ V∖S: capacity of the cut = sum of capacities of edges from S to V∖S. The minimal cut is the "bottleneck" of the network.

Ford-Fulkerson Algorithm: we search for an "augmenting path" in the residual network: a path from s to t where each edge has a residual capacity > 0. We increase the flow along the path. We repeat until there is no such path.

Complexity: O(E · f_max) for rational capacities. The Edmonds-Karp algorithm uses BFS to find the shortest path → O(V E²).

Full Example Analysis: network: s→a (c=4), s→b (c=3), a→t (c=3), a→b (c=2), b→t (c=4).

Path 1: s→a→t, flow = 3. Path 2: s→b→t, flow = 3. Residual network: s→a (c=1), a→b (c=2). Path 3: s→a→b→t, flow = 1. Total max flow = 7. Minimum cut: {s,a,b} and {t} → capacity = 3 + 4 = 7. ✓

Matchings in Bipartite Graphs

Bipartite graph: V = A ∪ B, edges only between A and B.

Matching M: a set of edges with no shared vertices. Maximum matching is the largest M by number of edges.

Hopcroft-Karp Algorithm: O(E√V). Searches for augmenting paths using BFS (finds all shortest augmenting paths simultaneously), then DFS to find the maximum matching of this length.

Hungarian Algorithm (assignment problem): given a complete bipartite graph with weights wᵢⱼ (cost of assigning task i to executor j). Find the minimal assignment (= matching of minimal total weight). Complexity: O(n³).

Applications of matchings:

• Assigning teachers to classes in a school
• Distribution of orders among taxi drivers (Yandex.Taxi — a real-time matching problem!)
• Medicine: compatibility of kidney donors and recipients
• Recommendation systems: matching users with content

Minimum Spanning Tree (MST)

Spanning tree of a graph G = (V, E): a connected acyclic subgraph including all vertices. Number of edges = |V| − 1.

MST problem: find a spanning tree with the minimal total weight of edges.

Kruskal’s Algorithm: O(E log E)

1. Sort edges by weight
2. Iterate edges in ascending order
3. Add edge to T if it does not create a cycle (check via Union-Find)

Prim’s Algorithm: O(E log V) with heap

1. Start with any vertex
2. Add the minimal edge connecting tree T to an external vertex
3. Repeat until |V|−1 edges

Proof of optimality (cut property): for any cut (S, V∖S), the minimal edge through the cut belongs to any MST.

Full analysis: graph with 4 vertices: a-b (4), a-c (3), b-c (2), b-d (5), c-d (1).

Kruskal: edge sorting: c-d (1), b-c (2), a-c (3), a-b (4), b-d (5). Add: c-d (1) ✓, b-c (2) ✓, a-c (3) ✓. Tree: {c-d, b-c, a-c}. Weight = 6. The next edge a-b (4) would create a cycle a-b-c-a → skip.

Applications: laying cables for a network with minimal cable length (telephone, electrical networks), data clustering (single-linkage), approximation algorithms for TSP.

Shortest Paths

Dijkstra's Algorithm: non-negative weights. O((V+E) log V) with binary heap. Idea: greedily expand the "front" of shortest paths from s.

Bellman-Ford: allows negative weights (but not negative cycles). O(VE). Detects negative cycles.

Floyd-Warshall: all pairs shortest paths. O(V³). Simple implementation via DP.

A* Algorithm: heuristic acceleration of Dijkstra. With an admissible heuristic h(v) ≤ d(v,t) the algorithm explores fewer vertices. Used in GPS navigation, games, robot path planning. With h = 0 it degenerates to Dijkstra.