图的路径运算矩阵与哈密顿回路等路径问题  

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

作　　者：高遵海 陈倬 GAO Zunhai;CHEN Zhuo(School of Mathematics and Computer Science,Wuhan Polytechnic University,Wuhan 430048,China;School of Economics and Management,Wuhan Polytechnic University,Wuhan 430048,China)

机构地区：[1]武汉轻工大学数学与计算机学院,湖北式汉430048 [2]武汉轻工大学经济与管理学院,湖北式汉430048

出　　处：《华中科技大学学报（自然科学版）》2021年第2期32-36,共5页Journal of Huazhong University of Science and Technology(Natural Science Edition)

基　　金：国家自然科学基金资助项目(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-operation matrices.The power length formula of general path-operation matrix was proved,and the necessary and sufficient condition for the existence of Hamilton cycle in simple graph was obtained.By the analysis of the total time complexity of the matrix multiplication operation,it is found that the computation of this algorithm is less than that of other similar methods.A new research method for path problems in graph theory is presented.

关 键 词：路径运算矩阵 简单图 最长路 最短路 哈密顿回路 

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]