正确性证明:图论中树的直径算法

Question

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

不过我不知道如何证明这一点？我尝试过对节点数量的归纳,但是有太多的情况.

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

Answer 1

让我们调用第一个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来证明每个案例.

Answer 2

我要解决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属于一个最大的距离对.