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

Algebra Method of Calculating Paths in Graph and Some Applications

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

There are a pair of adjacent points vi→vj （ vi→vj ） in the directed graph G, the path can be expressed by polynormal as vi - vj, and dij expresses weight of the edge. Ω={0,1} , solving linear equations, then finding out dij. The results can be used to solve the shortest path and critical path in the directed graph G, in addition, it is effective in undirected graph, calculating Hamihonian path and circuit and Euler path and circuit.