图论中研究一类网络优化问题的理论和方法。 1955年，TE 在研究最大铁路吞吐量时首次提出了求给定网络上两点之间最大运输量的问题。 1956年，LR Ford、DR 等人提供了解决此类问题的算法，从而建立了网络流理论。所谓网络或容量网络是指一个连通的带权有向图D=(V,E,C)，其中V为图的顶点集，E为有向边（即弧）集，C为电弧容量。另外，顶点集合包括起点和终点。网络上的流是从起点到终点的可行流。这是网络上定义的非负函数。一方面，受到容量的限制。另一方面，除了起点和终点外，要求保持所有中间点的流入量和总和。流出是平衡的。如果将下图视为一个道路网络，则顶点v1...v6代表6个城镇，每条边上的权重代表两个城镇之间的道路长度。现在我们要问：如果将物料从起点v1运输到终点v6，应该选择哪条路线使总运输距离最短？这类问题称为最短路径问题。如果把上图看成一个石油管网，v1代表发送点，v6代表接收点，其他点代表中转站。每边的重量代表该管段的最大输送量。现在我们需要问如何安排石油管道，使v1到v6的总运输量最大化。这样的问题称为最大流问题。

最大流理论由Ford和于1956年创立，他们指出了最大流的流量值等于最小割（截距集）的容量这一重要事实，并基于这一原理，他们设计了一种方法是使用标记方法来查找最大值。流的方法后来又被一些人改进，使得求解最大流的方法更加丰富和完善。最大流问题的研究将图论与运筹学特别是线性规划紧密联系起来，开辟了图论应用的新途径。

假设G(V,E)是一个有限有向图，其每条边(u,v)∈E都有一个非负实数容量c(u,v)。如果(u,v)不属于E，我们假设c(u,v) = 0。我们区分两个顶点：源点s和汇点t。网络流是一个实数函数 f，对于所有节点 u 和 v 具有以下特征： V×V→R 容量限制 ( )： f (u, v) ≤ c (u, v) 一条边的流不能超过它的容量。斜对称（Skew）：f(u,v)=-f(v,u) 从u到v的净流量必须与从v到u的净流量相反（参见示例）。 （既然想看网络流量，这个是必须要知道的） 流量守恒（Flow）：除非u=s或u=t，否则Σ(w∈V)f(u,w)=0 的净流量除了“制造”流的源点和“消耗”流的汇点之外，节点为零。请注意，f(u,v) 是从 u 到 v 的净流量。如果该图表示一个真实网络，其中包含 4 个单位的从 u 到 v 的实际流量和 3 个单位的从 v 到 u 的实际流量，则 f(u, v) = 1 且 f(v,u) = − 1 。

边的剩余容量( )为cf(u,v)=c(u,v)−f(u,v)。这根据 Gf(V,Ef) 定义了剩余网络 ( )，它显示了有多少可用容量。请注意，即使原始网络中没有从 u 到 v 的边，在剩余网络中也可能存在从 u 到 v 的边。由于相反方向的流动相互抵消，减少从 v 到 u 的流动等于增加从 u 到 v 的流动。扩展路径 (Path) 是一条路径 (u1,u2...uk)，且 u1 =s, uk =t且cf(ui,ui+1)>0，这意味着可以沿着该路径传输更多的流。