期刊论文

Path-operation matrices of graph for solving Hamilton cycles and other path problems

中文

华中科技大学学报(自然科学版)

1671-4512

2021

49

2

32-36

10.13245/j.hust.210204

61179032:国家自然科学基金 11301405:国家自然科学基金

本校为第一机构

从简单图的邻接矩阵定义了初始路径运算矩阵和一般路径运算矩阵,并定义了一般路径运算矩阵的加法和乘法运算,通过这些运算可以直接求简单图的最长路、最短路、任意两点之间的通路及具有长度约束的路径问题,还可以检测简单图哈密顿回路及计算所有哈密顿回路,结果都显示在最后的路径运算矩阵上.证明了一般路径运算矩阵的幂长公式并得到了简单图存在哈密顿回路的充要条件,分析了矩阵乘法运算的总时间复杂度,结果表明本算法比其他同类方法计算量大大减少,为图论相关路径问题研究提供了一个新的研究方法.

The initial path-operation matrix and general path-operation matrix were derived from the adjacent matrix of a simple graph.The addition and multiplication operation of the general path-operation matrices were defined, which can be used to solve some path problems, such as the longest path, the shortest path, the path between any two points, and path problems with length constraints.This method can also determine whether Hamilton cycles exist or not and if they exist can find out all of them.The desired results were all showed in the final path...