无向正权网络最短路模型的建立和理论分析  

Founding a model of the shortest path in undirected network with positive weight and analyzing it in theory

作　　者：乞建勋[1] 苏志雄[1] 张立辉[1] 

机构地区：[1]华北电力大学经济与管理学院,北京102206

出　　处：《系统工程理论与实践》2012年第10期2221-2228,共8页Systems Engineering-Theory & Practice

基　　金：国家自然科学基金(70671040);华北电力大学博士研究生创新资助项目

摘　　要：路径问题是运筹学的重要分支,更是图论学科成立的奠基问题.针对无向网络中的路径问题,首先,建立了无向正权网络最短路模型,提出一些能够反映无向网络中节点、边和路线规律性的参数概念,包括点参数和边参数,用这些参数代替边的权数描述无向正权网络;其次,通过对模型进行理论分析,推导出与各参数相关的结论,利用参数揭示了点、边、路线以及无向正权网络之间的关系,并初步体现了该模型的用途;第三,利用该模型求解了与无向正权网络相关的几类基本路径问题;最后,通过应用举例,阐述了该模型的部分应用.需注意的是,该模型也适用于带回路的有向正权网络.The path problem is an important branch of operations research, and it is even more the foundation problem of founding graph theory subject. Aiming at the path problem in undirected network, firstly, a model of the shortest path in undirected network with positive weight was founded, several con- ceptions of parameters contain node parameters and edge parameters were proposed which could represent regulation of node, edge and path in undirected network, and undirected network was described by these parameters instead of edge weight; secondly, by analyzing the model in theory~ conclusions relevant to these parameters were deduced, relations among node, edge, path and undirected network were revealed by using these parameters, and function of the model was realized in a certain extent; thirdly, several basic path problems which related to undirected network with positive weight were solved by using the model; and finally, partial application of the model was validated by illustrating. It should be noticed that this model is also applicable to directed network with positive weight and loop.

关 键 词：运筹学 最短路模型 无向正权网络 点参数 边参数 

分 类 号：O221[理学—运筹学与控制论]