Conne tivity and Flows

The notion of connectivity captures, as the word says, how well a graph is connected. A graph that is a tree, has the minimum possible connectivity: if any edge or vertex is removed (for example, a computer or a channel in a communication network fails) the graph becomes disconnected. As another example, think of the vertices of the graph corresponding to round-abouts and the edges corresponding to stretches of road that connect these roundabouts. The connectivity expresses how “easy it is to travel from one roundabout to the other”. If there is heavy traffic all along a particular path P1 that connects roundabouts A to B, to avoid the traffic we would like to use a different path P2 that does not have any common road stretch with P1. Or we may even want to use a path P3 that does not even cross path P1 at roundabouts, as presumably if there is traffic on P1 there may also be traffic at the roundabouts. In this lecture, we are going to talk and distinguish between vertex connectivity, and edge connectivity. Let G = (V,E) be a graph (network) with the set of vertices V and the set of edges E ⊂ V × V. Definition 4.1. A vertex cut between two vertices S and R is a set of vertices whose removal disconnects S from R. A min-vertex-cut is a cut with the smallest (minimal) value. With every edge e of the graph, we can in general associate a parameter ce ≥ 0 that expresses the capacity of the edge. That is, if we were to imagine the edge being a pipe, how many units of water can simultaneously flow throug