采用算法方法计算两条路径强积的边不规则强度

《Ain Shams Engineering Journal》：Computing the edge irregularity strength of the strong product of two paths using an algorithmic approach

　　

本研究针对两条路径强积 Pm? Pn的边不规则标注（edge irregular labeling）开展算法化求解。两条路径的积可形成正方形或矩形网格结构，研究人员通过变化 m 与 n 的取值覆盖所有可能情形。为实现最优标注，研究设计了两种图遍历算法的实现方案：行遍历法（row-method）与矩阵遍历法（matrix-method），前者为一维遍历，后者为二维遍历。实验结果表明，矩阵遍历法可获得最优顶点标号，是本研究的核心成果。基于曲线拟合分析，研究人员给出了边不规则强度的上界 ?(V+E)/2?。所设计的算法可推广至相似图族或其他类型的标注问题，在通信网络信道分配、并行处理任务调度、网格计算资源优化及交通网络路径规划等领域具有实际应用价值。

论文解读：《采用算法方法计算两条路径强积的边不规则强度》

该研究由 M. Shahzad、M.A. Asim、R. Hasni 与 A. Ahmad 合作完成，发表于《Ain Shams Engineering Journal》。研究聚焦于图论中边不规则强度（edge irregularity strength, es(G)）的计算难题，针对两条路径的强积（strong product of two paths, P_m? P_n）这一特殊图结构展开算法化求解。边不规则强度是指为使图中所有边的权值（由端点顶点标号之和定义）互不相同，所需的最小顶点标号最大值，其精确计算长期缺乏通用高效方法，尤其对于结构复杂的积图而言，传统数学推导难以覆盖所有参数组合。该研究通过引入计算实验范式，弥补了强积图边不规则强度精确值的空白，同时提出的算法框架可迁移至其他图族的标注问题。

研究人员采用的关键技术方法包括：设计双模式图遍历标注算法，分别实现一维行遍历与二维矩阵遍历的标号分配逻辑；构建动态种子初始化机制，通过多组初始值迭代筛选最优解；引入曲线拟合分析方法，基于大规模计算结果推导理论上界；开发唯一性校验模块，实时检测边权冲突并回溯调整顶点标号。实验覆盖 m、n 取值范围从 2 到 400 的多种组合，包含正方形与矩形两类拓扑结构。

2.1 基于行遍历法的强积标注

该方法沿水平维度逐行分配顶点标号，将顶点分为四类分别计算。首行顶点按自然数序列递增标号；非首行首列顶点依据上方、左上方及右上方的相邻边权确定唯一标号；边界顶点则简化邻接参考集。以 5×5 的 P₅? P₅为例，行遍历法得到的最大顶点标号为 46，对应 es(P₅? P₅)=46。该方法逻辑简单但标号增长较快，易导致边权分布不均衡。

2.2 基于矩阵法的强积标注

矩阵法采用二维双向遍历策略，以逐步扩展的正方形子网格为单位进行标号。算法首先为 2×2 子网格分配初始种子标号（如 1、5、2、3），随后逐层扩展至 3×3、4×4 直至完整 m×n 网格，每扩展一层仅计算新增行列的顶点标号，并依据邻接边权唯一性约束动态调整。对于矩形结构（m≠n），先对 min(m,n)×min(m,n) 的正方形区域应用矩阵法，剩余部分按行列方向线性延伸标注。实验显示，5×5 网格的矩阵法最大标号为 44，优于行遍历法。

2.3 算法结果比较

对比实验表明，矩阵法的边不规则强度值显著低于行遍历法，且随 m、n 增大优势更明显。例如 100×100 网格中，矩阵法结果为 20656，而行遍历法高达 33617。矩阵法获得的边权分布更均衡，曲线增长平缓，证明其标号分配效率更高，能有效降低顶点标号的最大值。

2.4 计算复杂度分析

算法的时间复杂度由主导循环决定。外层循环运行 O(min(m,n)) 次，内层嵌套循环呈三角形模式，复杂度为 O(min(m²,n²))；后续的扩展标注与边权校验循环复杂度为 O(max(m,n))。综合来看，整体时间复杂度为 O(max(m³,n³))，即随 m、n 中较大值呈立方级增长，符合网格规模扩大的计算开销规律。

讨论与上界推导

研究人员将算法结果与理论分析结合，提出强积图边不规则强度的紧上界 ?(V+E)/2?，其中 V 为顶点数、E 为边数。该上界与算法结果高度接近且始终大于算法值，验证了算法的近似最优性。通过与二部图 K_m,n的对比发现，P_m? P_n的 es 值显著高于同规模二部图，反映出强积图因边密度更高导致标注难度更大。研究同时证实，矩阵法在标号效率与计算稳定性上均优于传统行遍历策略，可作为积图标注的标准算法范式。

结论部分指出，该研究首次实现了 P_m? P_n边不规则强度的系统化计算，所提上界是当前已知的最优结果。算法框架可直接应用于通信网络信道分配、并行计算任务调度、网格资源优化等场景，为图标注问题的计算化解决提供了可复用的方法论。