Flows and Connectivity

Often one is interested in how connected a graph is, that is how easy is it to get from one vertex to another and how resilient a graph is to losing edges or vertices. This last notion of connectivity is particularly useful in computer networks where one doesn't want a network or even the entire internet to fall apart when a handful of computers or wires are removed for maintenance or by viruses. In this module we will examine how cutting edges in a network is related to the flow of some quantity such as data through the network (for a more physical analogy you can also think in terms of water flowing through pipes). Our ultimate goal is to show that the largest number of distinct (i.e. using different edges) routes between two vertices in a graph is equal to the minimal number of edges that can be cut to separate those vertices.

Activity 1

Verify that the minimal number of edges you can cut to separate s from t is equal to the number of routes from s to t which don't share edges in the following graphs.

The Setup

To start out we will assume that the graph G is directed. We distinguish two vertices in G as the source s of the flow and the sink t of the flow. For a vertex v we let the set O(v) correspond to the vertices which have an edge coming into them from v, and let I(v) correspond to the set of vertices which have an edge going into v. It is helpful to think of O(v) as where the flows moves out from v, and I(v) as from where the flow moves into v. Conceptually a flow is very simple: whenever there is an edge going from v to u we assign it a non-negative value f(v, u). We also assume that for each vertex besides s and t the flow going in is equal to the flow going out (i.e. our vertices aren't leaky). Mathematically this means that for all v besides s and t we have:

With this condition in hand we can tell something about the flow at both s and t. If we sum the above relation over all vertices besides s and t the edges going into and out of s and t are still involved in the calculation. In particular this means that the net flow leaving the source has to be the same as the net flow entering the sink. This means that

We define this quantity as the value or amount of the flow from s to t, and denote it by v(f).

Activity 2

On the following graph the flow out of s is given to you. Fill in valid flow values for the other edges. Remember that the sum over the edges going into a vertex has to equal the sum over the the edges leaving the vertex. What happens at t?

Cutting Edges

To study how cutting edges affects the flow we define a capacity c for each edge and make f(u, v) ≤ c(u, v). Capacity is an intrinsic property of the graph and thus controls what flows are possible, much like how the diameter of pipes controls how much water can flow through the pipes. For two sets of vertices X and Y we define E(X, Y) as the set of all edges starting in X and ending in Y. We then let f(X, Y)=Σf(x,y) and c(X,Y)=Σc(x,y) where the sums are taken over the edges in E(X, Y). For notational convenience we will assume that f(u, v) = c(u, v) = 0 when the edge (u, v) is not present in the graph.

A cut separating s and t is a set of edges given by E(S,V-S) where S is a set of vertices containing s but not t. Removing the edges in a cut stops all flows from s to t, that is it makes v(f)=0. We define the capacity of a cut E(S,V-S) as c(S,V-S). This is at least as large as the value of any flow as the entire flow had to cross over the edges in E(S,V-S) to get from s to t. We can conclude that the minimal capacity of all cuts is at least as large as the maximum value of any flow.

In fact the minimal capacity is actually equal to the maximum flow: there exists a flow which uses all the capacity of the minimal capacity cut. This is known as the max-flow min-cut theorem The idea behind the theorem is quite simple, and involves building the set S recursively. Suppose f is a flow with maximum value. We start by putting the source s in S. We then apply the following rule for adding vertices to S: if v is in S and the vertex u is such that c(v, u)>f(v, u) or f(u, v)>0 then we add u to S. The rule is then applied to u, and so on until we cannot add anymore vertices to S.

Activity 3

For the graph below find the set S described above. Assume that each edge has capacity 5. Each edge is labeled with its flow. What is the capacity of the cut and the value of the flow?

The sink t will never be in S, because if it were we could use the condition c(v, u) > f(v, u) to show that there is another flow f' with a larger value than f. Since t is not in S, E(S,V-S) is a cut. The maximality of v(f) also means that we can't possibly find a cut with smaller capacity. This means that S is exactly the cut we wanted. The last thing we need to check is that the value of f is the same as the capacity of the cut.

We can calculate the v(f) simply by checking how much flow is leaving/entering S:

By how we defined S the edges in E(S, V-S) must have f(v, u)=c(v, u), so the first sum in v(f) is just c(S, V-S). Similarly the condition that f(u, v)>0 forces each term in the second sum to be 0. Thus v(f)=c(S, V-S) for a maximal flow f.

Menger's Theorem

We are now ready to achieve our goal, Menger's theorem, which states that for any two distinct vertices s and t of an undirected graph the minimal number of edges we can cut to separate s from t is equal to the maximal number of paths from s to t which do not share any edges (these paths are edge-disjoint). Here a path just means a sequence of edges we can follow to get from s to t. To apply the max-flow min-cut theorem we replace each edge in G by two directed edges going in opposite directions.

To show Menger's Theorem we assign each edge capacity 1. Since we have restricted the capacity to be 1, the capacity of a cut is equal to the number of edges, k, in the cut. Next we need to account for paths from s to t. One particular consequence of the max-flow min-cut theorem is that if the capacity function takes only integer values then there is some flow with maximum value which also takes only integer values. Thus there is a maximal flow on the graph for which each edge has flow 0 or 1.

For a flow to have maximal value it must be that each of the edges in the cut is assigned value 1, which means that this flow is going through each edge in the cut. If there were more than k edge-disjoint paths from s to t some of them would have to share edges as they go through this cut. This isn't possible, so there are at most k edge-disjoint paths from s to t. Additionally, some configuration of these k paths must not share any edges, as otherwise there would be a cut with less than k edges somewhere in the graph. Thus Menger's theorem holds.

Go Back