边数确定的无向图的简单路径条数最大值

· · 算法·理论

起因是洛谷省选计划答疑有人问了，然后我不会做，也没搜到，后来问了下 Tony2 老师得到了答复，感觉很聪明于是记录一下。

问题是，给定 m，求有 m 条边的无向图的简单路径条数最大值，但是这东西显然确切解很困难，即使是求大概的复杂度也比较难，所以求一个它的对数的界。

有构造，将一堆四元环 a, b, c, d 连起来，就是 a 连前面的 d 连后面的环，显然路径数大概是 m^2 2 ^ {m/4} 左右的，取对数是 \Theta(m)。

有上界是（假设连通）所有点的度数加一的乘积，因为每个点只能走一次，所以考虑选择一个后继的边，不用考虑是否组成路径。度数加一之和是 O(m) 的，而把一个数 x 拆成一些数的乘积使其最大，这是经典问题，答案是 3^{x/3} 左右的，于是原问题对数的上界就是 O(m)。复杂度上界是 O(3 ^ {m})。

于是就得到了原问题对数的一个复杂度的界。

但是还不知道更进一步怎么做！原问题能不能确定最优解的复杂度呢！更进一步，能不能确定最优解的具体解析解呢！大家教教。以及有相关文章也欢迎评论！

有一个优化的构造方式是，如果能找到一张图，使得花费了 a 条边，从某个出发点到某个终止点有 b 条路径，那就有一个 \Theta(b ^ {\frac{m}{a}}) 的构造方法。

2025-2-23 13:45 UPD：adjective 老师提出了，如果确定起点为某个点的话，令 f _ m 表示简单路径数，那么有 f_i \le \max_{d=1}^{i} df_{i-d} + 1，f_0 = 1。也就是，把 m 拆成一列数字 a _ 1, \ldots, a _ k，然后是它的所有后缀的乘积之和。最优解里数列一定是单调不降的，而且开头不会有太多的 1（有多个的话合并起来答案不变），所以这个最大值和所有数乘积最大值同阶，就是 O(3 ^ {\frac{m}{3}})，再乘上开始的点的选法就是 O(m3 ^ {\frac{m}{3}})，于是上界变小了！

2025-3-3 14:55 UPD：如果允许重边，就可以造一个 \frac m 3 个点的环，这样就是 O(m3^{\frac{m}{3}}) 的路径数了，达到了上界（）