版权说明 操作指南
首页 > 成果 > 详情

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

认领
导出
Link by 中国知网学术期刊 Link by 万方学术期刊
反馈
分享
QQ微信 微博
成果类型:
期刊论文
论文标题(英文):
Path-operation matrices of graph for solving Hamilton cycles and other path problems
作者:
高遵海;陈倬
作者机构:
[高遵海] 武汉轻工大学数学与计算机学院
[陈倬] 武汉轻工大学经济与管理学院
语种:
中文
关键词:
路径运算矩阵;简单图;最长路;最短路;哈密顿回路
期刊:
华中科技大学学报(自然科学版)
ISSN:
1671-4512
年:
2021
卷:
49
期:
02
页码:
32-36
基金类别:
国家自然科学基金资助项目(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...

反馈

验证码:
看不清楚,换一个
确定
取消

成果认领

标题:
用户 作者 通讯作者
请选择
请选择
确定
取消

提示

该栏目需要登录且有访问权限才可以访问

如果您有访问权限,请直接 登录访问

如果您没有访问权限,请联系管理员申请开通

管理员联系邮箱:yun@hnwdkj.com