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

问题描述 投票：16回答：4

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

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

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

algorithm tree graph-theory proof-of-correctness
4个回答
15
投票

让我们调用第一个BFS x找到的端点。关键的一步是证明在第一步中找到的x始终“有效” - 也就是说，它始终位于某条最长路径的一端。 （请注意，通常可以有多个同样最长的路径。）如果我们可以建立这个，那么很容易看到以x为根的BFS会尽可能地从x找到一个节点，因此必须是整体最长的路径。

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

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

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

[编辑2]稍后再回过头来看，现在我认为需要考虑的两个案例是（i）uv路径与从根到x的路径相交（在某个顶点y，不一定在uv处）路径的最高点h）; （ii）它没有。我们仍然需要h来证明每个案例。

7
投票

我要去找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属于一个最大的遥远对。

0
投票

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

假设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中有两个顶点，那么它们共享一条边）。可以证明，具有v作为一个端点的G中的最大简单路径都具有p的并集的形式，其中从中心到叶子的简单路径仅遍历绿色边缘。

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

0
投票

1：procedureTreeDiameter（T）

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

3：u = BFS（T，v）

4：t = BFS（T，u）

5：返回距离（u，t）

结果：复杂度= O（| V |）

最新问题
© www.soinside.com 2019 - 2024. All rights reserved.