7.1 The Maximum-Flow Problem and the Ford-Fulkerson Algorithm

The Problem Motivation:

A few concepts: to model transportation networks–networks whose edges carry some sort of traffic and whose nodes act as “switches” passing traffic between different edges. Network models of this type have several ingredients: capacities on the edges, indicating how much they can carry; source nodes in the graph, which generate traffic; sink (or destination) nodes in the graph, which can “absorb” traffic as it arrives; and fina~y, the traffic itself, which is transmitted across the edges.

Flow Networks definition: a flow network is a directed graph G = (V, E) with the following features. Associated with each edge e is a capacity, which is a nonnegative number that we denote ce.

a Flow network is a directed graph G = (V, E) with the following features. o Associated with each edge e is a capacity, which is a nonnegative number

that we denote ce.

o There is a single source node s e V. o There is a single sink node t ~ V