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

Question

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

虽然我不确定如何证明这一点？我曾尝试在节点数量上使用归纳，但情况太多。

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

Answer 1

我们称之为第一BFS X中发现的端点。关键的一步是证明在第一步中发现的x总是“有效” - 也就是说，它始终处于某条最长路径的一端。 （请注意，一般情况下，可能有多条同样最长的路径。）如果我们可以建立这个路径，可以很容易地看到以x为根的BFS将尽可能地从x找到一些节点，因此它必须是一个整体最长的路径。

提示：假设（相反）在两个顶点u和v之间存在较长的路径，它们都不是x。

注意到，在u和v之间的唯一路径上，必须有一些最高（最接近根）顶点h。有两种可能性：h从BFS的根到x的路径上，或者不是。通过显示在两种情况下，u-v路径至少可以通过用x的路径替换其中的某个路径段而形成矛盾。

[编辑]实际上，可能没有必要分别处理这两种情况。但是我经常发现把配置分解成几个（或者甚至很多）情况并且分别处理每个配置更容易。这里，h在从BFS根到x的路径上的情况更容易处理，并给出了另一种情况的线索。

[编辑2]说回这个以后，现在看来，我认为这两种情况需要考虑是：（i）紫外线路径贯穿从根x的路径（在一些顶点y，不一定在uv路径的最高点h）;和（ii）它没有。我们仍然需要h来证明每个案例。

Answer 2

我要去努力j_random_hacker's hint。让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属于最大限度遥远对。

Answer 3

下面看它的另一种方法：

假设ģ =（V，È）是一个非空，与顶点有限树设置V和边缘套E。

考虑下面的算法：

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

这基本上是从叶子向内着色的图形，用绿色标记与叶子最大距离的路径，并标记只有较短距离为红色的路径。同时，Ç，中心，具有较短的最大距离到叶节点被缩减距离，直到Ç仅包含与对叶的最大的最大距离的一个或两个节点。通过构造，从叶顶点到它们最近的仅穿过绿色边缘的中心顶点的所有简单路径长度相同（计数），以及从叶顶点到其最近中心顶点的所有其他简单路径（遍历在至少一个红色边缘）更短。此外可以证明，

• 该算法总是给出的条件下终止，留下的ģ每个边沿染成红色或绿色，并留下Ç与一个或两个元件。
• 在算法终止，d是ģ直径，在边缘测量的。
• 给定一个顶点v在V，在ģ最大长度简单路径起始于v正是那些含有包含中心的所有顶点，终止于叶，并只遍历中心和远端点之间的绿色边缘。这些从中心到离中心最远的一片离开v。

---

现在考虑你的算法，这可能是更实用，在上面的光。从任何一个顶点v开始，恰好有一个简单的路径p从顶点，在中心顶点结束，并包含中心的所有顶点（因为摹是一棵树，如果有是两个顶点C然后它们共享边缘）。可以示出具有v作为一个端点都具有p的并集与从中心到叶片遍历仅绿色边缘的简单路径的形式中ģ最大简单路径。

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