网络理论

编辑:外宾网互动百科 时间:2020-01-28 04:10:28
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
在图论基础上研究网络一般规律和网络流问题各种优化理论和方法的学科,是运筹学的一个分支。网络是用节点和边联结构成的图,表示研究诸对象及其相互关系,如铁路网、电力网和通信网等。
中文名
网络理论
性    质
理论
属    性
网络
国    家
德国

网络理论西默尔

编辑
(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。戴克斯特拉法可以通过编制计算程序,在计算机上运算。

网络理论最短树问题

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

网络理论最小费用流

编辑
网络理论 网络理论
在网络中,若每条边【vi,vj】除容量cij外,还给一个数aij,表示从vivj运输单位物资所需
网络理论 网络理论
支付的费用,则问题便是寻找一个可行流{fij},其流值为给定的数值r*,并使总费用取最小值。这样的可行流称为最小费用流。最小费用流问题可用对应于线性规划的原始算法和对偶算法求解。例如,若对偶算法是:从各边流fij=0和流值r=0的最小费用流开始,如果r<r*,则采用以费用作边长求最短路径的方法寻找关于{fij}的增广链,把{fij}调整为流值r′(r<r′≤r*)的最小费用流,直到流值为r*为止。

网络理论参考书目

编辑
网络理论 网络理论
网络理论 网络理论
陈树柏:《网络图论及其应用》,科学出版社,北京,1982。
网络理论 网络理论
L.R.Jr.Ford and D.R.Fulkerson,Flows in Networks,Princeton Univ. Press, N.J.,1962.  T.,Integer Programming and Network Flows,Addison-Wesley 1969.
词条图册 更多图册
词条标签:
非自然 非社会 自然学科 科技产品 科技 社会 理学 互联网