本博文用来记录在学习网络流过程中的一些知识点。
首先，要认定网络流建图为有向图：
【容量网络】
图G（V，E）为有向网络，在V中指定一个源点和一个汇点，流量从源点出发经过有向网络流向汇点。对于每一条有向边有权值C，称作弧的容量。有向边称为弧。这样的有向网络称为容量网络。
【弧的流量】
容量网络G中的每条弧上的实际流量称作弧的流量。
【网络流】
有向图G中弧上流量的集合，称为网络流。
【可行流】
在容量网络中满足下列条件的网络流称为可行流。
1、弧流量限制：流量要大于等于0且小于等于弧的容量。
2、平衡条件：流量只能从源点流出经过容量网络在汇点会聚。在网络中不会凭空出现和消失。
【可行流流量】
源点的净流出流量或汇点的净流入流量。
【零流】
流量为零。
【伪流】
满足限制条件但不满足平衡条件的网络流。也称为容量可行流。
【最大流】
在容量网络中，满足弧流量限制条件和平衡条件的最大可行流，称为网络最大流，简称最大流。
【饱和弧与非饱和弧】
在容量网络中的某一条弧当流量等于容量时，此弧为饱和弧，否则为非饱和弧。
【零流弧和非零流弧】
在容量网络中的某一条弧当流量等于零时，此弧为零流弧，否则为非零流弧。
【链】
在容量网络中，顶点序列（U1，U2……Un，V）为一条链，要求两个相连的点之间有一条弧。
注意：链和有向图中有向路径不是相同概念，有向路径中有向边的方向是相同的，但链这里不要求这样。
【正方向】
设P为容量网络中源点到汇点的一条链，由源点到汇点的方向就为正方向。
【前向弧与后向弧】
方向与链的正方向相同的弧称为正向弧。反之称为后向弧。
【增广路】
在容量网络中P是从源点到汇点的一条链，如果：
1、P的所有前向弧都为非饱和弧。
2、P的所有后向弧都为非零流弧。
则称P是一条增广路（增广链或可改进路）。
沿着增广路改进可行流的操作称为增广。
【残留容量】
对于给定的容量网络中某条弧的容量为C，流量为F，残留容量就位C-F。
【残留网络】
以残留容量建成的容量网络。也称为剩余网络。
【割】
在容量网络G（V，E）中存在E‘为E的子集。若G在删掉E‘的所有边后不连通，E‘就为G的割。因为割将G的顶点集划分为S，T两个集合。所以记割为（S，T）。若源点s在点集S中，汇点t在点集T中，则称该割为S-t割。
【割的容量】
割的所有前向弧（定义源点到汇点为正方向）的容量只和。
【最小割】
割的容量最小的割称为最小割。
【割的净流量】
割中所有弧的流量之和，前向弧流量为正值，后向弧的流量为负值。
【增广路定理】
若容量网络中可行流f已经为最大流的充要条件是在容量网络中不存在增广路。
【最大流最小割定理】
对于容量网络G，其最大流量等于最小割流量。