39

为了找到树的直径，我可以从树中取出任何节点，执行 BFS 以找到离它最远的节点，然后在该节点上执行 BFS。与第二个 BFS 的最大距离将产生直径。

不过，我不确定如何证明这一点？我尝试过对节点数使用归纳法，但是案例太多了。

任何想法将不胜感激......

4

4 回答 4

25

让我们调用第一个 BFS x 找到的端点。关键的一步是证明在第一步中找到的 x 总是“有效的”——也就是说，它总是在某个最长路径的一端。（请注意，一般情况下，可能有不止一条等长的路径。）如果我们能确定这一点，很容易看出以 x 为根的 BFS 会找到离 x 尽可能远的某个节点，因此它必须是一个整体最长的路径。

提示：假设（相反地）在两个顶点 u 和 v 之间有一条更长的路径，这两个顶点都不是 x。

观察到，在 u 和 v 之间的唯一路径上，必须有一些最高（最接近根）的顶点 h。有两种可能性：要么 h 在从 BFS 的根到 x 的路径上，要么不在。通过表明在这两种情况下，通过将其中的某些路径段替换为到 x 的路径，可以使 uv 路径至少与它一样长。

[编辑]实际上，毕竟可能没有必要分别处理这两种情况。但我经常发现将配置分解为几个（甚至多个）情况并分别处理每个情况更容易。这里，h 在从 BFS 根到 x 的路径上的情况更容易处理，并为其他情况提供了线索。

[编辑 2]稍后再谈，现在在我看来，需要考虑的两种情况是 (i) uv 路径与从根到 x 的路径相交（在某个顶点 y，不一定在 uv路径的最高点 h); (ii) 它没有。我们仍然需要 h 来证明每种情况。

于 2013-11-16T03:49:28.870 回答
13

我要解决j_random_hacker 的提示。让我们s, t成为最远的一对。设u为任意顶点。我们有一个类似的示意图

    u
    |
    |
    |
    x
   / \
  /   \
 /     \
s       t ,

哪里x是交点s, t, u（即位于这些顶点之间的三个路径中的每一个上的唯一顶点）。

假设v是一个与 最大距离的顶点u。如果原理图现在看起来像

    u
    |
    |
    |
    x   v
   / \ /
  /   *
 /     \
s       t ,

然后

d(s, t) = d(s, x) + d(x, t) <= d(s, x) + d(x, v) = d(s, v),

其中不等式成立，因为d(u, t) = d(u, x) + d(x, t)和d(u, v) = d(u, x) + d(x, v)。有一种对称的情况，即在 和v之间s而x不是在x和之间t。

另一种情况看起来像

    u
    |
    *---v
    |
    x
   / \
  /   \
 /     \
s       t .

现在，

d(u, s) <= d(u, v) <= d(u, x) + d(x, v)
d(u, t) <= d(u, v) <= d(u, x) + d(x, v)

d(s, t)  = d(s, x) + d(x, t)
         = d(u, s) + d(u, t) - 2 d(u, x)
        <= 2 d(x, v)

2 d(s, t) <= d(s, t) + 2 d(x, v)
           = d(s, x) + d(x, v) + d(v, x) + d(x, t)
           = d(v, s) + d(v, t),

所以max(d(v, s), d(v, t)) >= d(s, t)通过平均参数，并且v属于一个最大距离的对。

于 2015-03-23T20:04:26.270 回答
1

这是查看它的另一种方法：

假设G = ( V , E ) 是具有顶点集V和边集E的非空有限树。

考虑以下算法：

  1. 让count = 0。让E中的所有边最初都是无色的。让C最初等于V。
  2. 考虑 V 的子集V '包含所有具有恰好一条未着色边的顶点：
    • 如果V ' 为空，则令d = count * 2，然后停止。
    • 如果V ' 恰好包含两个元素，则将它们的相互（未着色）边缘着色为绿色，让d = count * 2 + 1，然后停止。
    • 否则，V '至少包含三个顶点；进行如下：
  3. 将计数加一。
  4. 从C中删除所有没有无色边的顶点。
  5. 对于V中具有两个或多个未着色边缘的每个顶点，将其每个绿色边缘重新着色为红色（某些顶点可能具有零这样的边缘）。
  6. 对于V ' 中的每个顶点，将其未着色的边缘着色为绿色。
  7. 返回步骤 (2)。

这基本上是从叶子向内为图形着色，将与叶子的最大距离标记为绿色，将距离较短的路径标记为红色。同时，中心C的节点与叶子的最大距离较短，直到C仅包含一个或两个与叶子的最大距离最大的节点。

通过构造，从叶顶点到其最近中心顶点且仅穿过绿色边缘的所有简单路径的长度相同（计数），并且从叶顶点到其最近中心顶点（至少穿过一条红色边缘）的所有其他简单路径是更短。还可以证明

  • 这个算法总是在给定的条件下终止，让G的每条边都被染成红色或绿色，而C留下一个或两个元素。
  • 在算法终止时，d是G的直径，以边缘为单位测量。
  • 给定V中的顶点v，从v开始的G中的最大长度简单路径恰好包含包含中心的所有顶点、终止于叶子并且仅遍历中心和远端点之间的绿色边缘的路径。这些从v穿过中心，到达离中心最远的叶子之一。

现在考虑一下你的算法，根据上述情况，它可能更实用。从任何顶点v开始，从该顶点恰好有一个简单的路径p，结束于一个中心顶点，并包含该中心的所有顶点（因为G是一棵树，如果C中有两个顶点，那么它们共享一条边）。可以证明，G中以v为端点的最大简单路径都具有p的并集形式，其中一条从中心到叶的简单路径仅穿过绿色边缘。

我们目的的关键点是另一个端点的传入边缘必须是绿色的。因此，当我们从那里开始搜索最长的路径时，我们可以访问那些仅从叶子穿过（所有顶点）中心到另一个叶子的绿色边缘的路径。这些正是G中的最大长度简单路径，因此我们可以确信第二次搜索确实会揭示图形直径。

于 2017-02-06T21:44:32.140 回答
-4

1：程序树直径（T）

2：选择任意顶点v，其中v∈V

3:u = BFS (T, v)

4:t = BFS (T, u)

5：返回距离（u，t）

结果：复杂度 = O(|V|)

于 2019-04-12T02:43:06.367 回答