1. 研究目的与意义（文献综述）

1.1 目的及意义

现实中的许多问题都可以转化为最大流问题。最大流问题是经济学和管理学中的一类典型问题。在一个网络中每段路径都有“容量”和“费用”两个限制的条件下，此类问题的研究试图寻找出：流量从a到b，如何选择路径、分配经过路径的流量，可以在流量最大的前提下，达到所用的费用最小的要求。如n辆卡车要运送物品，从a地到b地。由于每条路段都有不同的路费要缴纳，每条路能容纳的车的数量有限制，最小费用最大流问题指如何分配卡车的出发路径可以达到费用最低，物品又能全部送到。

网络或者网络流是一种基本的数据结构，而最大流则是网络流上的基本问题。网络本质上是一个符合一定条件的有向带权图。而最大流是最大可行流的简称，可行流是一个定义在网络流上的符合一定条件的函数。

2. 研究的基本内容与方案

2.1研究的基本内容

流网络中每条有向边可以认为是传输物质的管道，每个管道有固定的容量，可以看作是物质能够流经该管道的最大速度。顶点是管道之间的交叉连接点，除了汇点之外，物质只流经这些点，不会再顶点滞留或消耗。也就是说，物质进入某顶点的速度必须等于离开该顶点的速度。这一特性被称为“流守恒”(flow conservation)。例如图中的电路原理图，根据基尔霍夫电流定律，在每个交叉连接点出，流进的电流等于流出的电流。电流的定义为单位时间内通过导线某一截面的电荷量，即为电荷的流动速度。所以，用流守恒的观点可以理解为：电荷量流进某交叉顶点的速度等于离开该顶点的速度。

我们研究的基本内容便是最大流问题，这是流网络中最简单的问题：在不违背容量限制的条件下，求解把物质从源点传输到汇点的最大速率。

3. 研究计划与安排

第1周—第3周 搜集资料，撰写开题报告；

第4周—第5周 论文开题；

第6周—第12周 撰写论文初稿；

4. 参考文献（12篇以上）

[1]徐俊明. 图论及其应用（第3版）. 合肥：中国科学技术大学出版社，2010.

[2]卜月华，王维凡，吕新忠. 图论及其应用(第2版).南京：东南大学出版社，2015.

[3]曹汝成. 组合数学（第二版）.广州：华南理工大学出版社，2012.