网络中的最小费用最大流问题二、基本概念与基本定理三、寻求最大流的标号法四、最小费用最大流问题一、引言2 网络系统的最大流问题 一、引言 在许多实际的网络系统中都存在着流量和最大流问题。例如铁路运输系统中的车辆流，城市给排水系统的水流问题等等。而网络系统流最大流问题是图与网络流理论中十分重要的最优化问题，它对于解决生产实际问题起着十分重要的作用。3 网络系统的最大流问题图8.23是一个网络vtv3v2v1v4vs1735108611453Cij每一个弧旁边的权就是对应的容量（即最大通过能力）。要求指定一个运输方案，使得从vs到vt的货运量最大，这是寻求网络系统的最大流问题。4 网络系统的最大流问题二、基本概念与基本定理 定义8.5 设一个赋权有向图D =（V,A）,在v中指定一个发点（或源点）vs和一个收点（或汇点）vt,其他的点叫做中间点。对于D中的每一个弧（vi,vj）A,都有一个权 cij 叫做弧的容量。我们把这样的图 D 叫做一个网络系统，简称网络，记做D =（V，A，C）。 网络D上的流，是指定义在弧集合A上的一个函数f=f(vi,vj)=fij f(vi,vj)=fij叫做弧
