计算图中路径问题的代数方法及其应用

作者：耿涛

来源：大连大学学报, 2009, 30(06): 1-5.

• Grdbner基
• 约化
• 路径
• 权值

对于一个给定的有向图G,G中两个相邻顶点vi→vj的路径可以用多项式vi→vj来表示,并用dij记其边的权值,而dij可由在Ω={0,1}的范围内解线性方程组来确定。该结果可以用来解决有向图的最短路径、关键路径等问题,并且此方法还可推广到无向图,用来解决哈密顿道路和回路,欧拉道路和回路等问题。

• 单位
  海南大学