如何计算无向多重图中两点间无重复边的简单通路数量？

问题描述 #

我拥有一个无向多重图，希望计算给定两点间简单通路（允许顶点重复，但不允许边重复）的数量。请问是否存在简便可行的方法？

我想到两种可能的思路：

• 找出所有长度小于图规模的通路，再剔除存在重复边的通路。但问题在于第一步生成的集合规模可能极大。
• 在每条边中间插入一个2阶顶点，将多重图转化为普通图。这种方法在计算上可行，但对于我研究的图来说耗时可能较长。

我认为肯定有前人研究过此类问题，恳请各位提供建议。

补充说明 #

我当前研究的图结构类似ϕ符号，其三条臂分别替换为更小的ϕ；接着将新生成的九条中间臂再替换为更小的ϕ，以此类推。

可行方法建议 #

针对你的问题，结合图的分形递归特性，给出几个高效的解决方向：

1. 基于分形递归结构的动态规划 #

你的图是自相似的递归分形结构，这是核心突破口。可以定义以下递归状态：

• f(n, u, v)：第n阶分形子图中，从顶点u到v的边不重复通路数量
• g(n, u)：第n阶分形子图中，从顶点u出发回到自身的边不重复回路数量
  通过分析高阶子图与低阶子图的拼接逻辑（比如高阶子图的臂由低阶完整ϕ结构替换而成），推导状态转移方程。这种方法无需遍历所有通路，直接利用递归特性计算，时间复杂度远低于暴力枚举。

2. 边图（Line Graph）建模+递归计算 #

把原问题转化为边图上的路径计数：

• 将原无向图的每条边作为边图的一个顶点
• 若原无向图中两条边共享一个顶点，则在边图中对应的两个顶点间连一条边
  此时，原问题中s到t的边不重复通路，等价于边图中所有以s关联边为起点、t关联边为终点的路径数量，再加上s与t之间的直接边（若存在）。结合分形结构的递归性，可先计算低阶边图的路径数，再组合得到高阶结果，比直接转化全图后暴力计算高效得多。

3. 参考分形图路径计数的已有研究 #

这类问题属于欧拉通路相关的计数范畴，针对分形图的研究已有不少成熟结论：

• 分形图的自相似性天然适配组合数学中的递推关系，可查找“分形图 边不重复通路计数”“自相似图 路径数递推”相关文献，很多同类型结构已存在现成的递推公式。
• 对于多重图，可先将同顶点间的多条边视为带标签的独立边，再结合递归拆分逻辑计算。

对原有思路的优化 #

• 针对“插入2阶顶点”的方法：不要直接处理完整大图，先计算低阶子图的通路数，再通过子图拼接的组合规则推导高阶结果，大幅降低计算量。
• 暴力枚举思路直接放弃，分形图规模随阶数指数增长，枚举会直接导致计算爆炸。

内容的提问来源于stack exchange，提问作者Daron