Many problems in computer science can be represented by a graph
consisting of nodes and links between them. Examples are *network flow* problems,
which involve transporting goods or material across a network, such as a railway system.
You can represent a network flow by a graph whose nodes are cities and whose
arcs are rail lines between them. (They're called *flows* because their properties
are similar to those of water flowing through a network of pipes.)

A key constraint in network flows is that each arc
has a *capacity* — the maximum amount
that can be transported across the arc in a fixed period of time.
The *maximum flow problem*
is to determine the maximum total amount that can be transported across all arcs in the
network, subject to the capacity constraints.

The first person to study this problem was the Russian mathematician A.N. Tolstoi, in the 1930s. The map below shows the actual railway network for which he wanted to find a maximum flow.

OR-Tools provides several solvers for network flow problems in its graph libraries.

The following sections present examples of network flow problems and show how to solve them: