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

Application of Grbner basis to the shortest route

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

There are a pair of adjacent joints xi and xj. Let the length of route from xi to xj be aij, and they can be expressed by a polynormal as xj-xi-aij. Categorizing all this kind of polynomals in the graphic according to their leading terms, and sequencing this categories, they form a polynomial table F. If there is a shortest route between xm and xk, which are random knots in the graphic, the Grbner basis of generated idea by the set of polynomials is {1}. Assumeing what we research is the shortest route from xm to xk, using xk-xm reducing the unit of table F according to a sequence, a constant through reduction can be got, and then point xm can reach point xk. Because there are many different routes between xm and xk, there are a group of constants through different sequences of reduction. The minimal constant is the shortest route.