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