树中三个最远节点中的两个必须位于直径上

Question

我正在努力寻找一组三个节点（a、b、c），以最大化 a、b 和 c 之间路径上的唯一边数 - {P(a,b) U (P(b, c) U P(a,c)} 其中 P(x,y) 是 x 和 y 之间的路径（边）（下面的正式定义）。

正式定义，P - 路径，E - 边

我已经开发了一种算法来实现这一点，但我正在努力证明其正确性。我需要证明这三个节点中的两个必须位于树直径上。然而，我被困在这一点上，似乎无法前进。

我的算法：

1. 求直径 (a, b)
2. 删除直径上的边，这会将树分成不相交的子树
3. 使用直径上每个节点的 DFS 作为根找到最深的节点。 （该节点是 c）
4. 返回a、b、c

Answer 1

用反证法很容易证明。假设 (a,b)、(b,c)、(c,a) 都不位于直径上。将包含所有三个顶点的子树称为 S。它有一个顶点 r，使得 (a,r)、(b,r) 和 (c,r) 没有公共边。然后我们可以找到直径 (d,e) 并构建更大的顶点集。

考虑几种情况： (1) (d,e) 与 S 不相交； (2) (d,e)与S有1个公共顶点，为r； (3) (d,e) 与 S 有一个或多个公共顶点，并且它们都位于 (a,r) 上； (4) (d,e) 与 S 有一个或多个公共顶点，并且它们都位于 (a,r) 和 (b,r) 上。 （其他情况对称）。在每种情况下，很容易看出存在一个包含 d 和 e 的三元组，其边集大于 (a,b,c) 的边集。