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

摘要

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