证明正确性：算法的树图论直径 [英] 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.

任何的想法会大大AP preciated ...

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是从BFS到根的路径上的X，或者它不是。通过显示，在这两种情况下，该紫外线路径可以至少只要通过与路径到x替换一些路径段在它制成显示出矛盾。

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.

其实，这可能不是必要的治疗2例分别毕竟。但我经常发现很容易突破的配置分成几个（甚至很多）的情况下，并分别对待每个人。这里，其中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）紫外线路相交的路径从根到x（在部分的顶点Y，不一定是UV路径的最高点h）;和（ii）它没有。我们仍然需要小时，以证明每个案件。

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屋！