# Flows, connectivity and matching

Definition 3..1 (Flow)

A flow in a digraph with source and sink is a function such that where (the flow out of ) and (the flow into ). Convenient to set if .

Definition 3..2 (Directed edge)

is the directed edge from to . Loops and multiple edges are forbidden, so certainly or .

Observation 3..3

We imagine as representing a flow of water or electricity in a network, being pumped in at , and being pumped out at . The condition expresses that flow is conserved at each vertex.

Definition 3..4 (Value of the flow)

is called the value of the flow where is the source and is the sink.

Definition 3..5 (Net flow)

Let with and . Let . The net flow from to is .

Since we get .

Definition 3..6 (Capacity function)

Given a capacity function we require that for all .

Definition 3..7 (Cut)

Let with and . Let . The set of edges is called a cut with capacity .

For any cut we have .

Theorem 3..8 (Max-flow min-cut (MFMC))

The maximum value of a flow (source and sink ) in a network is equal to the minimum cut capacity.

Proof. The maximum flow in a network is less than or equal to the minimum cut capacity. Let be a flow. We construct . Initially let . Then put if either or with . Repeat.

If then there is a sequence of vertices starting with where for each either or . Let . We construct a new flow equal to except on the path but with or as appropriate. is a flow. so was not maximal, contradiction.

Algorithm increases. Take a subsequence monotonic on each edge. Take the limit. This flow has value of limit so it is maximal.

If . Let . is a cut. For every with and we have . For every edge , we have . . That is, the value of the flow is the cut capacity of some cut.

Corollary 3..9 (Integrability theorem)

In a network with integer valued edge capacities there is a maximal flow whose value is equal to the minimum cut capacity, which has integer values at each edge.

Proof. Follow MFMC starting with the zero flow. Then is always integer.

Observation 3..10

Note that there may be a maximal flow which is not integer valued on each edge.

Definition 3..11 (Multiple sinks and sources)

Consider multiple sources and multiple sinks . The value of the flow is and a cut is where and .

Corollary 3..12 (MFMC for multiple sources and sinks)

In a multiple source network the maximum value of a flow is equal to the minimum cut capacity.

Proof. We construct a new network by joining a supersource to and a supersink to using edges of infinite capacity.

Apply MFMC. Note that any cut of finite capacity cannot touch edges or so cut can be applied to original graph.

Definition 3..13 (Vertex capacities)

We can consider vertex capacities instead of edge capacities. The capacity function is now and we want . A cut is now a set of vertices such that has no path. It has capacity .

Corollary 3..14 (Vertex capacity version of MFMC)

The maximum value of a flow in a network with vertex capacities is equal to the minimum cut capacity.

Proof. Construct from a new network with edge capacities. Replace each vertex by two vertices and and an edge . For each edge add an edge to . We give capacity give infinite capacity. Apply MFMC.

John Fremlin 2010-02-17