给定规模连通图的最大平均路径长度上界及公式规律问询

链图（N个顶点线性相连的无向结构）是同规模无向图中平均路径长度最长的类型，因此其平均路径长度即为该规模图的平均路径长度上界。

公式规律拆解 #

你推导的分段公式可按N的奇偶性梳理核心规律：

• 奇数N：公式为 $\frac{N^2 - 1}{6}$

  • 增长趋势：平均路径长度随N的平方级增长，这是因为链图中远距离顶点对的数量随规模平方增加；
  • 修正项：减1是为了让分子$(N^2-1)$能被6整除——奇数的平方减1等价于$(N-1)(N+1)$，是两个连续偶数的乘积，必然包含2和3的因数，因此能被6整除；
  • 系数6：由链图中所有顶点对的路径长度求和后，除以总顶点对数$\frac{N(N-1)}{2}$化简得到。

• 偶数N：公式为 $\frac{N^2}{4}$

  • 增长趋势：同样保持平方级增长，与奇数情况的增长逻辑一致；
  • 系数4：偶数规模的链图可对称划分为两个等长的子链，路径长度的统计结果经过化简后，最终得到除以4的形式。

小例验证 #

• N=2（偶数）：平均路径长度为1，代入公式得 $\frac{2^2}{4}=1$，匹配；
• N=3（奇数）：平均路径长度为$\frac{4}{3}$，代入公式得 $\frac{3^2-1}{6}=\frac{8}{6}=\frac{4}{3}$，匹配。

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