最大流最小割定理是网络流理论的重要定理。是指在一个网络流中，能够从源点到达汇点的最大流量等于如果从网络中移除就能够导致网络流中断的边的集合的最小容量和。即在任何网络中，最大流的值等于最小割的容量。

现实生活中，人们经常见到一些网络，如铁路网、公路网、通信网、运输网等等。这些网络有一个共同的特点，就是在网络中都有物资、人或信息等某种量从一个地方流向另一个地方，如何安排这些量的流动以便取得最大效益是一个很有意义的实际问题。50年代福特（Ford）、富克逊（Fulkerson）建立的“网络流理论”，是网络应用的重要组成部分。

给定指定的一个有向图，其中有两个特殊的点源S(Sources)和汇T(Sinks)，每条边有指定的容量(Capacity)，求满足条件的从S到T的最大流(MaxFlow)。

割是网络中定点的一个划分，它把网络中的所有顶点划分成两个顶点集合S和T，其中源点,汇点。记为，满足条件的从S到T的最小割（Min cut）。

定理一：

如果f是网络中的一个流，是任意一个割，那么f的值等于正向割边的流量与负向割边的流量之差。

证明：

设X和Y是网络中的两个顶点集合，用表示从X中的一个顶点指向Y的一个顶点的所有弧（弧尾在X中，弧头在Y中）的流量和。只需证明：即可。

下列结论成立：

如果X∩Y=，那么： 成立。

根据网络流的特点：

如果V既不是源点也不是汇点，那么：；任何一个点，流入的与流出的量相等。

如果V是圆，那么：。

对于S中的所有点V都有上述关系式，相加得到： 。

又因为： 。

所以： 定理得证。

推论一：

如果f是网络中的一个流，是一个割，那么f的值不超过割的容量。

推论二：

网络中的最大流不超过任何割的容量。

定理二：

在网络中，如果f是一个流，是一个割，且f的值等于割的容量，那么f是一个最大流， 是一个最小割。

证明：

令割的容量为C，所以流f的流量也为C。假设另外的任意流，流量为，根据流量不超过割的容量，则,所以f是最大流。假设另外的任意割，容量为，根据流量不超过割的容量，所以有,故，是最小割。

在任何的网络中，最大流的值等于最小割的容量。

结论一：

最大流时，最小割中，正向割边的流量=容量，逆向割边的流量为0。

结论二：

在最小割中：

源点s属于S。

如果i属于S，结点j满足：有弧，并且或者有弧，并且那么j属于S。否则不是最小割。即从s出发能找到的含有残留的点组成集合S，其余的点组成集合T。

1.源点s属于S。

2.如果i属于S，结点j满足：有弧，并且,或者有弧，并且那么j属于S。否则不是最小割。即从s出发能找到的含有残留的点组成集合S，其余的点组成集合T。

问题描述：

某软件公司有n个可选的程序项目，其中第i个项目需要耗费资金元，开发成功后可以获得的收益为

元。

程序项目之间不是独立的：开发第i个项目的前提条件是必须先开发出一些其他的项目，这些项目成为第i个项目的“前驱项目”。已经给出所有项目的和以及前驱项目，请帮助该公司从这n个程序项目中选择若干个进行开发，使获得的总收益最大。

分析：令，净收益。可以获得利润的项目集合。：亏损的项目集合。

构造网络图：。

1、两类顶点：个点：原点s个汇点t，第i个项目点。

2、三种弧：如果，存在弧,容量为

如果，存在弧,容量法|

如果i个前驱项目为j，存在弧，容量为。

构造割，如果，则i的前驱。这对应一种实验方案。最大收益为。