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

Question

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

algorithmtreegraph-theoryproof-of-correctness

42

为了找到一棵树的直径，我可以从树中任选一个节点，执行 BFS 查找距离该节点最远的节点，然后对该节点执行 BFS。第二次 BFS 的最大距离将得出树的直径。

不过我不确定如何证明这个算法的正确性？我已经尝试使用节点数量归纳，但有太多情况需要考虑。

非常感谢任何想法...

- AYR

1

你能告诉我"too many cases"是什么意思吗？理论上，所有的子情况也都应该通过归纳法得到证明。 - Rahul Shardha

4个回答

16

我将处理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)，其中 x 是在路径上连接 s 和 t 的节点。还有一种对称的情况，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),

通过平均论证，有 v 属于最大距离对，因此 max(d(v, s), d(v, t)) >= d(s, t)。

- David Eisenstat

1

这里有一种替代的看法：

假设G = (V, E) 是一个非空、有限的树，其中顶点集为V，边集为E。

考虑以下算法：

令count = 0。初始时，E中的所有边均未着色。令C初值等于V。
考虑子集V'，其中包含恰好一个未着色边的所有顶点：
- 如果V'为空，则令d = count * 2，并停止。
- 如果V'恰好包含两个元素，则将它们的相互（未着色）的边涂成绿色，令d = count * 2 + 1，并停止。
- 否则，V'至少包含三个顶点；按以下方式继续：
将count增加一。
从C中删除所有没有未着色边的顶点。
对于V中有两个或更多未着色边的每个顶点，将其每个绿色边重新涂成红色（某些顶点可能没有这样的边）。
对于V'中的每个顶点，将其未着色边涂成绿色。
返回步骤(2)。

基本上，它从叶子向内着色图形，用绿色标记具有到叶子的最大距离路径，并用红色标记仅具有较短距离的路径。与此同时，中心C的节点，其最大距离到叶子更短，将被削减，直到C仅包含具有最大距离到叶子的一个或两个节点。

通过构造，所有从叶顶点到其最近中心顶点的简单路径只遍历绿色边缘的长度相同（count），而所有其他从叶顶点到其最近中心顶点的简单路径（至少遍历一条红色边缘）都更短。此外，可以证明：

该算法在给定条件下总是终止，使得G的每条边都着了红色或绿色，并且让C只有一个或两个元素。
在算法终止时，d是以边计量的G直径。
给定V中的顶点v，在G中从v开始的最长简单路径恰好包含所有中心点，以叶子结尾，并且只在中心点和远端之间穿过绿色边。这些路径从v开始，穿过中心，到达距中心最远的叶子节点之一。

现在考虑你的算法，它可能更实用，基于上述内容。从任何一个顶点v开始，存在一条简单路径p，以中心顶点结束，并包含中心的所有顶点（因为G是一棵树，如果C中有两个顶点，则它们共享一条边）。可以证明，在G中以v为一端点的最大简单路径都具有从中心到叶子的只遍历绿色边的简单路径的形式。

对我们来说关键的一点是，另一端点的入边必定是绿色的。因此，当我们从那里开始搜索最长路径时，我们可以访问从叶子到另一个叶子穿过（所有中心的）只有绿色边的路径。这些路径恰好是G中最大长度的简单路径，因此我们可以确信第二次搜索将确实显示出图的直径。

- John Bollinger

-4

1:procedureTreeDiameter(T)

2:选择任意一个顶点v，其中v∈V

3:u = BFS ( T, v )

4:t = BFS ( T, u )

5:返回 distance ( u, t )

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

- Sadaf Najam

3

问题要求解释算法为什么有效，而不是算法的步骤。 - nullptr

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- j_random_hacker · Accepted Answer

让我们称第一个BFS找到的端点为x。关键步骤是证明此第一步找到的x始终有效 - 也就是说，它始终位于某条最长路径的一端。（请注意，通常可能存在多条同样长的路径）。如果我们能够证明这一点，那么很容易看出以x为根的BFS将会找到离x最远的一些节点, 这些节点因此必须是整个最长路径。

提示: 假设（相反）存在两个顶点u和v之间有更长的路径，其中都不包含x。

请注意，在u和v之间的唯一路径上，必须存在某个最高的（距根节点最近的）顶点h。有两种可能性：要么h在从BFS到x的路径上，要么不在。通过显示在两种情况下，可以用路径替换为一条通向x的路径来使u-v路径至少与原先一样长来证明矛盾。

[编辑]实际上，在处理2种情况之后可能不需要分别处理。但我经常发现将配置拆分为几个（甚至许多）案例并单独处理每个案例更容易。在这里，h在从BFS根到x的路径上的情况更容易处理，并为其他情况提供了线索。

[编辑2]回头看，现在似乎需要考虑的两种情况是(i) u-v路径与从根到x的路径相交（在某个顶点y处，不一定在u-v路径的最高点h处）；以及(ii)它们没有相交。我们仍然需要h来证明每种情况。