Combinatorics (Fall 2010)/Flow and matching

Flow

The maximum flow problem

An instance of the maximum flow problem consists of:

• a directed graph [math]\displaystyle{ G(V,E) }[/math];
• two distinguished vertices [math]\displaystyle{ s }[/math] (the source) and [math]\displaystyle{ t }[/math] (the sink), where the in-degree of [math]\displaystyle{ s }[/math] and the out-degree of [math]\displaystyle{ t }[/math] are both 0;
• the capacity function [math]\displaystyle{ c:E\rightarrow\mathbb{R}^+ }[/math] which associates each directed edge [math]\displaystyle{ (u,v)\in E }[/math] a nonnegative real number [math]\displaystyle{ c_{uv} }[/math] called the capacity of the edge.

The quadruple [math]\displaystyle{ (G,c,s,t) }[/math] is called a flow network.

A function [math]\displaystyle{ f:E\rightarrow\mathbb{R}^+ }[/math] is called a flow (or an [math]\displaystyle{ s }[/math]-[math]\displaystyle{ t }[/math] flow) in the network [math]\displaystyle{ G(V,E) }[/math] if it satisfies:

• Capacity constraint: [math]\displaystyle{ f_{uv}\le c_{uv} }[/math] for all [math]\displaystyle{ (u,v)\in E }[/math].
• Conservation constraint: [math]\displaystyle{ \sum_{u:(u,v)\in E}f_{uv}=\sum_{w:(v,w)\in E}f_{vw} }[/math] for all [math]\displaystyle{ v\in V\setminus\{s,t\} }[/math].

The value of the flow [math]\displaystyle{ f }[/math] is [math]\displaystyle{ \sum_{v:(s,v)\in E}f_{sv} }[/math].

Given a flow network, the maximum flow problem asks to find the flow of the maximum value.

The maximum flow problem can be described as the following linear program.

[math]\displaystyle{ \begin{align} \text{maximize} \quad& \sum_{v:(s,v)\in E}f_{sv}\\ \begin{align} \text{subject to} \\ \\ \\ \\ \end{align} \quad & \begin{align} f_{uv}&\le c_{uv} &\quad& \forall (u,v)\in E\\ \sum_{u:(u,v)\in E}f_{uv}-\sum_{w:(v,w)\in E}f_{vw} &=0 &\quad& \forall v\in V\setminus\{s,t\}\\ f_{uv}&\ge 0 &\quad& \forall (u,v)\in E \end{align} \end{align} }[/math]

The augmenting paths

Definition (Augmenting path)

Let [math]\displaystyle{ f }[/math] be a flow in [math]\displaystyle{ G }[/math]. A path [math]\displaystyle{ P=u_0u_1\cdots u_k }[/math] in the underlying undirected graph is an augmenting path to [math]\displaystyle{ u_k }[/math] if [math]\displaystyle{ u_0=s\, }[/math]; and for each edge [math]\displaystyle{ u_{i}u_{i+1} }[/math] in [math]\displaystyle{ P }[/math] we have [math]\displaystyle{ f(u_i,u_{i+1})\lt c(u_i,u_{i+1})\, }[/math] when [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math], and [math]\displaystyle{ f(u_{i+1},u_i)\gt 0\, }[/math] when [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math]. If [math]\displaystyle{ u_k=t }[/math], we simply call [math]\displaystyle{ P }[/math] an augmenting path.

For a flow [math]\displaystyle{ f }[/math] in [math]\displaystyle{ G }[/math], if there is an augmenting path [math]\displaystyle{ P }[/math], we can increase the flow [math]\displaystyle{ f(u_i,u_{i+1}) }[/math] of all edge [math]\displaystyle{ (u_{i},u_{i+1})\in E }[/math] by [math]\displaystyle{ \epsilon }[/math], and decrease the flow [math]\displaystyle{ f(u_{i+1},u_i) }[/math] of all edge [math]\displaystyle{ (u_{i+1},u_{i})\in E }[/math] by [math]\displaystyle{ \epsilon }[/math], without violating the capacity and conservation constraints.