Keywords:
Grdbner base; Reduced; The path; A weight
Grdbner 基;约化;路径;权值
Abstract:
Given a directed graph G, G of two adjacent vertex vi to vj paths can use
polynomial vi, vj, and dij remember the edge has a weight, and dij may consist in
Ω = {0, 1} within the scope of the solution system of linear equations to determine.
The results can be used to solve the shortest path and critical path problems of
directed graphs, and the method can also be extended to undirected graphs to solve
Hamiltonian roads and circuits, euler roads and circuits and other problems.
对于一个给定的有向图G,G 中两个相邻顶点vi → vj 的路径可以用多
项式vi → vj 来表示,并用dij 记其边的权值,而dij 可由在Ω={0,1} 的范围内
解线性方程组来确定。该结果可以用来解决有向图的最短路径、关键路径等问题,
并且此方法还可推广到无向图,用来解决哈密顿道路和回路,欧拉道路和回路
等问题。