给定大小的连通图的最大平均路径长度是多少？

Question

我正在寻找平均路径长度的上限作为 N（图形大小）的函数。

我知道它一定是链图（仅连接到最近邻居的顶点线），我得出以下公式：

我就是无法弄清楚其中的模式。

Answer 1

我不确定我是否理解了这个问题，但我会尝试：

• 1 / C. N 除以 2 等于 (N-2! * 2)/N! 并且可以简化为 2/(N * (N-1)) = 2/(N^2-N )
• 总和应为 (N^3 - N)/3（重新排列 Wolfram alpha 所说的内容，自从我的大学考试以来已经过去了太多时间）

所以整个东西完全等于 (N^2-1)/3(N-1) = (N+1)/3，计算起来非常简单，让我更加确信我不理解作业。