[科普中国]-网络理论

简介

在图论基础上研究网络一般规律和网络流问题各种优化理论和方法的学科，是运筹学的一个分支。网络是用节点和边联结构成的图，表示研究诸对象及其相互关系，如铁路网、电力网和通信网等。网络中的节点代表任何一种流动的起点、运转点和终点（如车站、港口、城镇、计算机终端和工程项目的事件等）。网络中的边代表任何物流、能流或信息流通过的通道（如输电线、通信线、铁路线和各事件之间的次序等）。在网络中每条边上赋予某个正数，称为该边的权，它可以表示路程、流量、时间和费用等。建立网络的目的都在于把某种规定的物质、能量或信息从某个供应点最优地输送到另一个需求点去。例如，在管道网络中要以最短的距离、最大的流量和最小的费用把水、石油或天然气从供应点送到用户那里。

发展概况网络理论起源于图论1。1845年G.R.基尔霍夫应用图论和2矩阵理论证明了电网络中两个重要定律，即基尔霍夫电流定律和电压定律，不仅为图论的发展作出了贡献，也奠定了网络理论的基础。20世纪50年代以来，随着网络理论的广泛应用，许多学者提出优化计算的方法。1956年L.R.小福特和D.R.富尔克森提出寻找最大流量的标号算法。1959年E.W.戴克斯特拉提出寻找最短路径的标号算法。1961年，富尔克森提出求解更一般的最小费用流的状态算法，这是解最短路径、最大流量与最小费用流的统一方法，是网络理论中最基本的结果之一。此后又相继提出了各种类型的网络流问题，诸如带下界容量的网络流、动态流、带增益的流和多种物资流等问题，并得到一系列结果。

最大流量问题当物质流或信息流通过给定的网络时（图1）,在流过每条边的流量xij不超过该边允许通过的流量cij的条件下,求出从发点s向收点t输出的最大流量f，即在满足的条件下,使f最大。最大流量问题是一个特殊的线性规划问题，有许多求解方法。一种有效的计算方法是福特-富尔克森法，它是根据最大流量-最小割集原理，通过标号算法，求出在上述约束条件下从发点s到收点t的最大流量f 的数值。其计算步骤如下：①绘制一个能满足上述约束条件的网络可行流（图2）。边上的数字为允许流量cij，括号内的数字为给定的可行流。②找出一条增广链。增广链是指从发点s到收点t的链中，满足正向边上xij0的链。图2中用粗线表示的{vs，v2,v3,v4,v6,vt} 是一条增广链。其中【v2,v3】为反向边,其余均为正向边。③调整可行流,即在增广链的各边上，属正向边加上一个修正量ε，属反向边减去一个修正量ε，即xij+εj，xji-εj。

最短路径问题一般提法是：寻找网络中两点间的最短路径,即寻找连接这两点的边的总权数(可以是距离、时间、费用等)为最小的通路。图4为最短路径问题的一个例子。最短路径问题有两种算法。戴克斯特拉法 1959年提出。其计算方法是：从始点vs,标以零值,并记在vs旁的方括号内。然后依节点序号顺序找出到达各点的最短距离,并说明来自何方,例如在节点v3处标上【v2,4】,即表示来自节点v2，距离累计为4。戴克斯特拉法可以通过编制计算程序,在计算机上运算。

最短树问题图6示出最短树问题的一个例子。一城市拟在6个地点架设电缆线路,每条边上的数字表示两点间的距离，要设计一个使电缆总长度为最短的铺设方案。求解最短树有两种方法。①克罗斯卡尔法:从两点间找出最短的边联结成一个最短支撑树(图7）。 ②破圈法：从网络的每一个圈中去掉具有最大权的边，直到无圈时为止，即可求出最短树（图8）。上述例子的计算结果是：最短树的总距离为17。最短树问题的求解可用于城市煤气和自来水管道、电话线、电缆等线路网络的优化问题。

最小费用流在网络中，若每条边【vi，vj】除容量cij外,还给一个数aij，表示从vi到vj运输单位物资所需支付的费用,则问题便是寻找一个可行流{fij},其流值为给定的数值r*，并使总费用取最小值。这样的可行流称为最小费用流。最小费用流问题可用对应于线性规划的原始算法和对偶算法求解。例如,若对偶算法是：从各边流fij=0和流值r=0的最小费用流开始,如果r