最大流问题

引例 （管道网络）现有如图9-37所示的输油管道网，vs为起点，vt为终点，v1，v2，v3，v4为中转站，其中每条边上的两个权数，前一个权数表示该管道的最大输油能力，后一个权数表示该管道现有输油量，问应如何安排各管道输油量，才能使从vs到vt的总输油量最大？

图9-37

管道网络中每条边的最大通过能力即容量是有限的，实际流量也并不一定等于容量，上述问题是讨论如何充分利用装置的能力，以取得最好效果（流量最大），这类问题通常称为最大流问题.

最大流问题是一类应用广泛的问题，例如在交通运输网络中有人流、车流、货物流，供水网络中有水流，金融系统中有现金流，通信系统中有信息流，等等.