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

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

路径问题是运筹学的重要分支,更是图论学科成立的奠基问题.针对无向网络中的路径问题,首先,建立了无向正权网络最短路模型,提出一些能够反映无向网络中节点、边和路线规律性的参数概念,包括点参数和边参数,用这些参数代替边的权数描述无向正权网络;其次,通过对模型进行理论分析,推导出与各参数相关的结论,利用参数揭示了点、边、路线以及无向正权网络之间的关系,并初步体现了该模型的用途;第三,利用该模型求解了与无向正权网络相关的几类基本路径问题;最后,通过应用举例,阐述了该模型的部分应用.需注意的是,该模型也适用于带回路的有向正权网络.

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.