正确性证明:图论中树的直径算法 [英] Proof of correctness: Algorithm for diameter of a tree in graph theory

问题描述

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

In order to find the diameter of a tree I can take any node from the tree, perform BFS to find a node which is farthest away from it and then perform BFS on that node. The greatest distance from the second BFS will yield the diameter.

不过，我不确定如何证明这一点?我试过对节点数使用归纳法，但是情况太多了.

I am not sure how to prove this, though? I have tried using induction on the number of nodes, but there are too many cases.

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

Any ideas would be much appreciated...

推荐答案

让我们调用第一个 BFS x 找到的端点.关键的一步是证明在第一步中找到的 x 总是有效"——也就是说，它总是在某个最长路径的一端.(请注意，通常可能存在不止一条同样长的路径.)如果我们可以建立这一点，很容易看到以 x 为根的 BFS 将找到离 x 尽可能远的某个节点，因此该节点必须是一个整体最长的路径.

Let's call the endpoint found by the first BFS x. The crucial step is proving that the x found in this first step always "works" -- that is, that it is always at one end of some longest path. (Note that in general there can be more than one equally-longest path.) If we can establish this, it's straightforward to see that a BFS rooted at x will find some node as far as possible from x, which must therefore be an overall longest path.

提示:假设(相反)两个顶点 u 和 v 之间有一条更长的路径，这两个顶点都不是 x.

Hint: Suppose (to the contrary) that there is a longer path between two vertices u and v, neither of which is x.

观察到，在 u 和 v 之间的唯一路径上，必须存在某个最高(最接近根)的顶点 h.有两种可能性:要么 h 在从 BFS 的根到 x 的路径上，要么不在.通过证明在这两种情况下，通过将其中的某些路径段替换为到 x 的路径，可以使 u-v 路径至少与 u-v 路径一样长，从而证明矛盾.

Observe that, on the unique path between u and v, there must be some highest (closest to the root) vertex h. There are two possibilities: either h is on the path from the root of the BFS to x, or it is not. Show a contradiction by showing that in both cases, the u-v path can be made at least as long by replacing some path segment in it with a path to x.

实际上，这两种情况毕竟可能没有必要分开处理.但是我经常发现将一个配置分解成几个(甚至很多)个案例，并分别对待每个案例更容易.在这里，h 在从 BFS 根到 x 的路径上的情况更容易处理，并且为另一种情况提供了线索.

Actually, it may not be necessary to treat the 2 cases separately after all. But I often find it easier to break a configuration into several (or even many) cases, and treat each one separately. Here, the case where h is on the path from the BFS root to x is easier to handle, and gives a clue for the other case.

稍后回到这个问题，现在在我看来，需要考虑的两种情况是 (i) uv 路径与从根到 x 的路径相交(在某个顶点 y，不一定在 uv 路径的最高点 h)；(ii) 没有.我们仍然需要 h 来证明每个案例.

Coming back to this later, it now seems to me that the two cases that need to be considered are (i) the u-v path intersects the path from the root to x (at some vertex y, not necessarily at the u-v path's highest point h); and (ii) it doesn't. We still need h to prove each case.

这篇关于正确性证明:图论中树的直径算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！