网络流相关
一、网络和网络流的基础概念
图论中的一种理论与方法，研究网络上的一类最优化问题。1955年，T.E.哈里斯在研究铁路最大通量时首先提出在一个给定的网络上寻求两点间最大运输量的问题。1956年，L.R.福特和D.R.富尔克森等人给出了解决这类问题的算法，从而建立了网络流理论。在一个公路网中，顶点v1…v6表示6座城镇，每条边上的权数表示两城镇间的公路长度。要问：若从起点v1将物资运送到终点v6去，应选择那条路线才能使总运输距离最短?这样一类问题称为最短路问题。如果在一个输油管道网中，v1表示发送点，v6表示接收点，其他点表示中转站，各边的权数表示该段管道的最大输送量。要问怎样安排输油线路才能使从v1到v6的总运输量为最大?这样的问题称为最大流问题。