Network Flows

• Network Flows consider a directed or undirected network
• Weight of an arc represents the capacity of that arc
• Capacity is the maximum amount of flow that can pass along the arc
• A vertex S is called a source if all arcs containing S are directed away from S
• A vertex T is called a sink if all arcs containing T are directed into T
• When showing a flow through a network, you must assign (non-negative) numbers to each arc such that:

  • the flow along each arc must not exceed the capacity
  • total flow into a vertex = total flow out of a vertex
• An arc is saturated if the flow is equal to the capacity
• Flows are the numbers going into the network
• A cut is a partition of the vertices into two sets, the source in one, the sink in the other
• The capacity of a cut is the maximum possible flow across the cut from S to T, without any regard to the rest of the network
• If a cut arc can only flow from T to S then it contributes to the capacity of the cut
• The Maximum Flow/Minimum Cut Theorem says that the maximum flow through a network equals the minimum cut
• When the maximum flow is reached, the cut is saturated
• In networks with more than one source and/or sink, you create a supersource and/or a supersink together with arcs of appropriate capacity
• The arcs leading from the supersource to each source must have total capacity equal to the total capacity leaving each source
• The arcs leading from each of the sinks to the supersink must have capacity equal to that arriving at each sink