4

我已经知道找到这里提到的树的直径的算法很长一段时间了：

  1. 选择一个随机节点 A
  2. 在此节点上运行 BFS 以查找距 A 最远的节点。将此节点命名为 S。
  3. 现在从 S 开始运行 BFS，从 S 中找到最远的节点，将其命名为 D。
  4. S和D之间的路径是树的直径。

但为什么它会起作用？

如果可以的话，我会接受Ivan和coproc的回答。这是两种非常不同的方法，它们都回答了我的问题。

4

5 回答 5

4

说S = [A - B - C - D - ... X - Y - Z]是树的直径。

考虑 中的每个节点S，比如说@，从它开始并“远离”直径，不会有比 更长的链min(length(@, A), length(@, Z))。

所以来自树上任何节点的dfs，它将在A或'Z'处结束，即直径的一端，再次来自它的dfs当然会引导你到树的另一边。

参考这个

在此处输入图像描述

于 2012-10-20T15:54:26.590 回答
3

假设您已经完成了步骤 1 和 2 并找到了 S，并且树中没有包含 S 的直径。选择树的直径 PQ。您基本上必须检查可能的情况，并且在所有情况下，发现 PS 或 SQ 至少与 PQ 一样长——这将是矛盾的。

为了系统地检查所有情况，可以假设树的根在 A。那么任意两个顶点 U 和 V 之间的最短路径按以下方式计算——设 W 为 U 和 V 的最低共同祖先。然后UV 的长度等于 U 和 W 之间以及 V 和 W 之间的距离之和 - 并且，在有根树中，这些距离只是节点级别的差异（并且 S 在这棵树中具有最大级别）。

然后分析 S 关于以 W 为根的子树（P 和 Q 的最低共同祖先）和顶点 P 和 Q 的所有可能位置。例如，第一种情况很简单 - S 不在以 W 为根的子树中. 然后，我们可以通过选择 P 和 Q 中离根更远的一个，并将其连接到 S 来简单地改进路径。其余情况类似。

于 2012-10-20T15:42:32.287 回答
2

该算法适用于任何无环图（树是一种特殊的无环图，因为它有一个根）。

可以通过选择任意两个附加点 S2 和 D2 并证明它们的距离 d(S2,D2) ≤ d(S,D) 来构建证明。从我们知道的算法

  • 通过步骤 2：d(A,S)≥d(A,D), d(A,S)≥d(A,S2), d(A,S)≥d(A,D2) 和
  • 通过步骤 3：d(S,D)≥d(S,A), d(S,D)≥d(S,S2), d(S,D)≥d(S,D2)。

通过区分最多 5 种情况（例如路径 SD 和 S2D2 没有公共边，路径 SD 和 S2D2 有公共边，A 连接到运行到 S 的边等。见下图）可以分解上述情况距离到子路径中，并根据子路径重写不等式。结论来自简单代数。细节留给读者作为练习。:-)

在此处输入图像描述

于 2012-10-20T15:59:46.040 回答
0

在我们开始证明之前有一些引理/事实。

  1. T 是一棵树，因此任何 2 对顶点之间恰好有 1 条路径。
  2. 如果 S--D 是直径，则源为 S（或 D）的 BFS 最终将给 D（或 S）最大距离。（根据直径的定义）

也让我们定义|XY| 为路径 X--Y 的长度。

定义 |XX| = 0。

令 A 为算法选择的随机节点。在步骤 2 之后，让最远的节点是 P。如果 P 是 S 或 D，那么使用引理 2我们就完成了。所以我们必须证明 P 必须是 S 或 D。

声明：如果 S--D 是直径，则 P 是 S 或 D。

证明：我将通过证明对立面来证明上述内容。证明适用于具有唯一直径的树，但对于非唯一直径，它也应该适用于微小的变化（主要是等式）。

如果 P 既不是 S 也不是 D，则 S--D 不是直径。

假设 P 既不是 S 也不是 D。

案例 1：路径 A--P 与 S--D 相交

在此处输入图像描述

让交点为 K。我们知道 BFS 将 P 标记为距 A 和引理 1最远的节点。

|美联社| > |AS|
 |AK| + |KP| > |AK| + |KS|

因此我们得到 |KP| > |KS|。

同样|KP| > |KD|。

现在我们考虑路径 SP

|SP| = |SK| + |KP|
 |SP| > |SK| + |KD|
 |SP| > |标清|

所以 SP 比直径长，这意味着 SD 不是直径。

案例 2：路径 A--P 不与 S--D 相交

在此处输入图像描述

现在我们知道 BFS 将 P 标记为最远节点。所以我们有

|美联社| > |广告|
 |美联社| > |AS|

我们可以写成 |AD| = |AK| + |KD| 其中K是直径中的一个顶点（包括S和D）。同样|AS| = |AK| + |KS|。

不失一般性假设 |AD|>=|AS|

|AK| + |KD| >= |AK| + |KS|
 |KD| >= |KS|

现在考虑路径 PD 

|PD| = |AP| + |广告|
 |PD| = |AP| + |AK| + |KD|
 |PD| > |美联社| + |KD| （|AK| > 0 因为 A 不能在直径上）
 |PD| > |KD| + |KD| (|AP| > |KD|)
 |PD| > |SK| + |KD| (|KD| >= |KS|)
 |PD| > |标清|

所以 SD 不是直径，因此不是索赔。

于 2013-09-08T13:45:06.487 回答
0

令 Set s 表示树的直径上的节点，A 和 Z 为末端节点，A 到 Z 的距离为直径。对于任何节点 n，它是 s 的成员，从 n 开始的最长可能路径将以 A 或 Z 结束。现在，如果您在树中选择一个 rand 节点 v，它要么是集合的成员，要么是在这个集合中有一个到节点 n 的路径。由于从 n 到的最长路径是 A 或 Z，并且从 v 到 n 的路径不能长于从 n 到 A 或 n 到 Z 的路径（如果是，则 v 必须是集合的成员）然后在任意节点 V 上运行 BFS 将首先找到 A 或 Z，随后的调用将找到互补的端点。不是数学女孩，只是抛出想法。

于 2013-11-26T21:27:14.513 回答