西默尔

（Georg Simmel,1858-1918) 德国著名社会学家，形式社会学的创始人，主要著作《社会分化论》《社会学》《社会学的根本问题》等。最早研究群体对个人行为的影响的社会心理学家，最早提出了传播网络理论，认为社会上的个人都是由特定的信息渠道相互连接的,要解释人的行为，就要了解其在传播链中的位置。西默尔把传播网络描绘为“舆论的厨房” 。

图片

简介

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

图片

发展概况

网络理论起源于图论。1845年G.R.基尔霍夫应用图论和矩阵理论证明了电网络中两个重要定律，即基尔霍夫电流定律和电压定律，不仅为图论的发展作出了贡献，也奠定了网络理论的基础。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的链中，满足正向边上xij<cij和反向边上xji>0的链。图2中用粗线表示的{vs，v2,v3,v4,v6,vt} 是一条增广链。其中【v2,v3】为反向边,其余均为正向边。③调整可行流,即在增广链的各边上,属正向边加上一个修正量ε,属反向边减去一个修正量ε,即xij+εj，xji-εj。εj值由下式决定:当xij<cij时

图片

图片

最短路径问题

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

图片

图片

最短树问题