Grobner基理论在最短路径问题中的应用

• 作者: 彭丰富 陈小松
• 来源期刊: 中南工业大学学报(自然科学版)
• 学科: 数学
• 关键词: 最短路径 Grbner基 约化
• 年，卷（期）: 2002,（6）
• 所属期刊栏目: 数学
• 页码范围: 648-650
• 页数: 3页
• 分类号: O157.6|O51.26
• 字数: 1717字
• 语种: 中文
• DOI: 10.3969/j.issn.1672-7207.2002.06.024

摘要

在最短路径问题中,若连通图中相邻节点对xi和xj间的路径长为aij,则节点之间的关系可用多项式xi-xj-aij描述,把所有的这种多项式以终点所表示的项为首项归纳和排序得到集合F,若存在最短路径供选择,则F生成理想的Grbner基为{1}. 因此,求节点xm到xk的最短路径,可用多项式xk-xm对F中的元素约化,所得到的一个常数就是这条可达路径的长度;若有多条路径可供选择,则每条路径对应一个常数,所有这些常数中的最小数就是最短路径的长度.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	陈小松	中南大学数学科学与计算技术学院	44	102	6.0	8.0
2	彭丰富	中南大学数学科学与计算技术学院	7	39	2.0	6.0