网络理论
网络理论
条目
历史版本
正文
在图论基础上研究网络一般规律和网络流问题各种优化理论和方法的学科，是运筹学 的一个分支。网络是用节点和边联结构成的图，表示研究诸对象及其相互关系，如铁路网、电力网和通信网等。网络中的节点代表任何一种流动的起点、运转点和终点（如车站、港口、城镇、计算机终端和工程项目的事件等）。网络中的边代表任何物流、能流或信息流通过的通道（如输电线、通信线、铁路线和各事件之间的次序等）。在网络中每条边上赋予某个正数，称为该边的权，它可以表示路程、流量、时间和费用等。建立网络的目的都在于把某种规定的物质、能量或信息从某个供应点最优地输送到另一个需求点去。例如，在管道网络中要以最短的距离、最大的流量和最小的费用把水、石油或天然气从供应点送到用户那里。
发展概况 网络理论起源于图论。1845年G.R.基尔霍夫应用图论和矩阵理论证明了电网络中两个重要定律，即基尔霍夫电流定律和电压定律，不仅为图论的发展作出了贡献，也奠定了网络理论的基础。20世纪50年代以来，随着网络理论的广泛应用，许多学者提出优化计算的方法。1956年L.R.小福特和D.R.富尔克森提出寻找最大流量的标号算法。1959年E.W.戴克斯特拉提出寻找最短路径的标号算法。1961年，富尔克森提出求解更一般的最小费用流的状态算法，这是解最短路径、最大流量与最小费用流的统一方法，是网络理论中最基本的结果之一。此后又相继提出了各种类型的网络流问题，诸如带下界容量的网络流、动态流、带增益的流和多种物资流等问题，并得到一系列结果。