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

StackOverflow https://stackoverflow.com//questions/20010472

题

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

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

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

有帮助吗？

解决方案

让我们召唤第一个BFS x找到的端点。重要的步骤证明了这个第一步中发现的X总是“作品” - 即，它总是在一些最长的路径的一端。 （注意，一般来说，可以有多个同样最长的路径。）如果我们可以建立它，那就很简单，看看X的BFS源于X将找到一些节点，因此必须是整体的最长的路径。

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

观察到，在U和V之间的唯一路径上，必须有一些最高的（最接近根）顶点h。有两种可能性：H从BFS根到X的路径上，或者它不是。通过表明在这两种情况下，可以通过将其中的某些路径段替换为X的路径来实现矛盾。

[编辑] 实际上，可能没有必要毕竟可以单独处理2个案例。但我经常发现将配置更容易地将配置分成几个（或甚至多个）案例，并单独对待每一个。这里，H位于来自BFS根到x的路径的情况更容易处理，并给出其他情况的线索。

[编辑2] 稍后返回此，现在在我看来，需要考虑的两个案例是（i）uv路径与根到x的路径与x相交（在一些顶点Y，不一定在UV路径最高点H）; （ii）它没有。我们仍然需要h证明每种情况。

其他提示

我要去锻炼 j_random_hacker 的提示. 。让 s, t 是距离最远的一对。让 u 是任意顶点。我们有一个类似的示意图

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

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

假设 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 属于最远距离对。

这是看它的另一种方法：

假设 g =（ v ， e ）是一个非空的有限树，带有顶点集 v 和边缘设置 e 。

考虑以下算法：

  1. Let Count = 0.让所有边缘 e 最初不可溶解。让 C 最初等于 V 。
  2. 考虑 v 的子集 v 包含所有顶点的 v
    • 如果 v '是空的，则让 d = count * 2，停止。
    • 如果 v '恰好两个元素然后颜色为它们的相互（未溶解）边缘绿色，让 D = 计数 * 2 + 1，停止。
      • 否则， v '包含至少三个顶点;按如下方式进行：
  3. 递增 count 一个。
  4. 删除具有没有未溶解边缘的 c 的所有顶点。
  5. 对于 v
  6. 为 v '中的每个顶点，颜色为uncororal Edge Green。
  7. 返回步骤（2）。

    8. 基本上颜色从叶子向内的图形，标记具有最大距离的路径与绿色的叶子，并标记在红色的距离中的较短距离。同时， c ，中心的节点，延伸到叶片的最大距离短，直到 C 仅包含与叶子最大距离最大距离的一个或两个节点。

    通过施工，叶顶的所有简单路径到其最近的中心顶点，即仅遍历绿色边缘的长度（ count ），以及从叶顶到其最近的中心的所有其他简单路径顶点（遍历至少一个红色边缘）较短。此外可以证明

    • 该算法总是在给出的条件下终止，离开<强> G C 与一个或两个元素。
      • 在算法终止时， D 是在边缘中测量的 G       的直径。 给出 v 中的顶点 v ， g < / strong>从 v 开始，其中包含中心的所有顶点，终止于叶子，只遍历中心和远端点之间的绿色边缘。这些从中中心的 v 从中心到距中心最远的叶子。

    现在考虑您的算法，这可能更加实用，鉴于上述情况。从任何Vertex V 开始，恰好有一个简单的路径 p 从该顶点，结束在中心顶点，并包含所有顶点中心（因为 G 是一棵树，如果 c 然后它们共享边缘） 。可以表明，<强> G 中的最大简单路径具有 v 作为一个端点，都具有 p 从中心到叶子的简单路径遍历绿色边缘。

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

1:procedureTreeDiameter(T)

2:pick an arbitrary vertex v where v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:return distance ( u, t )

Result: Complexity = O(|V|)

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top