首页 | 本学科首页   官方微博 | 高级检索  
     检索      

Grobner基理论在最短路径问题中的应用
引用本文:陈小松,彭丰富.Grobner基理论在最短路径问题中的应用[J].中南大学学报(自然科学版),2002,33(6):648-650.
作者姓名:陈小松  彭丰富
作者单位:中南大学,数学科学与计算技术学院,湖南,长沙,410083
摘    要:在最短路径问题中,若连通图中相邻节点对xi和xj间的路径长为aij,则节点之间的关系可用多项式xi-xj-aij描述,把所有的这种多项式以终点所表示的项为首项归纳和排序得到集合F,若存在最短路径供选择,则F生成理想的Grbner基为{1}. 因此,求节点xm到xk的最短路径,可用多项式xk-xm对F中的元素约化,所得到的一个常数就是这条可达路径的长度;若有多条路径可供选择,则每条路径对应一个常数,所有这些常数中的最小数就是最短路径的长度.

关 键 词:最短路径    Grbner基    约化
文章编号:1005-9792(2002)06-0648-03
修稿时间:2002年5月16日

Application of Grobner basis to the shortest route
Abstract:
Keywords:
本文献已被 万方数据 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号