March 4. Maximum flow and minimum cut I

Flow

Let D = (V, A) be a directed graph where every edge (i, j) has a capacity c_{ij} \in \mathbb{Z}_+. We are given two special vertices s,t where s is the source vertex and t is the sink vertex.  A flow in D is defined as function f: A \rightarrow \mathbb{Z}_+ where 0 \le f_{ij} \le c_{ij}. Further for every node v \notin \{s, t\} we have the following conservation property: \sum_{j: (j, i) \in A} f_{ji} = \sum_{j: (i, j) \in A} f_{ij}. In other words for every vertex that is not the source or the sink, the net incoming flow is the same as the net outgoing flow.

The value of the flow is given by val(f)=\sum_{j: (s, j) \in A} f_{sj} - \sum_{j: (j, s) \in A} f_{js}. We claim that val(f) = \sum_{j: (j, t) \in A} f_{jt} - \sum_{j:(t, j) \in A} f_{tj}. To see this consider a matrix where the rows are indexed by vertices and the columns are indexed by the edges. For any vertex v and edge (x, y) the entry (v, (x, y)) is equal to either f_{vy} if x=v and is equal to - f_{xv} if v=y. Otherwise the entries are 0. Note that the sum of the entries in a particular row gives us the net flow out of that vertex. Clearly the columns sum up to 0. Since the net flow for every vertex not equal to s,t is 0 the claim follows.

s-t Cut

An s-t cut is a subset S of edges such that A\setminus S has no directed path from s to t in D. We claim that the maximum number of s, t edge disjoint paths in D is the same as the size of the minimum s, t cut. Clearly the maximum is always less than the minimum. Menger’s theorem says that equality is attained, i.e. the maximum number of edge disjoint s, t path is equal to the size of the minimum s, t cut.

Thus our cut only consists of edges of the form (s, v) and (v, t). Define a flow f(i) = \min\{d_{in}(i), d_{out}(i)\}.

Claim: The maximum s,t flow in any graph D is less than or equal to the capacity of the s,t minimum cut.  The capacity of a cut (S, \bar{S}) is defined as c(S, \bar{S}) = \sum{i\in S, j\in \bar{S}} c_{ij}.

Proof: Note that f(s, V) - f(V, s) = val(f). For every x\neq s,t we have f(x, V) - f(V, x) = 0. Let us add up all the vertices in S. We get f(S, V) - f(V, S) = val(f). However f(S, V) = f(S, S) + f(S, \bar{S}). Thus f(S, \bar{S}) - f(\bar{S}, S) = val(f). This proves the claim.

Advertisements

One Comment

  1. Are the flow concepts not in our textbook? If so, are there other places we can look to find them?

    Reply

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s