Flows in networks

Introduction to Flows in Networks

• Network flow problem: A major problem where the aim is to find the maximum flow from a source to a sink in a directed graph, while respecting capacities attached to each edge.
• Conservation law: In absence of a source or sink, inbound flow equals outbound flow for an internal node.

Fundamental Terms

• Directed graph (digraph): A set of nodes and directed edges between them.
• Edge capacity: Maximum amount of flow that the edge can carry.
• Source (origin): Starting node from which flow is sent.
• Sink (destination): Node where flow is received.
• Cut: A partition of the nodes into two disjoint subsets that separates the source from the sink.

Algorithmic Approach

• Ford-Fulkerson algorithm: Algorithm used to find the maximum flow in a network.
• Augmenting path: Before the flow reaches its maximum, there is always a path from source to sink along which additional flow can be sent.
• Residual network: Directed network that represents the ‘leftover’ capacity after a flow.
• Bottleneck capacity: Smallest capacity on an augmenting path, determines how much extra flow can be pushed through.

Properties and Theorems

• Max-flow min-cut theorem: The maximum value of an s-t flow (from source to sink) is equal to the minimum capacity of an s-t cut in the network.
• Integral flow theorem: If all capacities are integers, then there’s a maximum flow that uses only integral flows.
• Flow Decomposition theorem: Any flow can be represented as a sum of path flows and cycle flows.

Key Points for Solving Flow Problems

• Start with an initial feasible flow (usually zero).
• Iterate until you find no more augmenting paths.
• To find augmenting paths more efficiently, use Breadth-First Search (BFS) or Depth-First Search (DFS).