为了找到树的直径,我可以从树中取出任何节点,执行 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.
更多推荐
正确性证明:图论中树的直径算法
发布评论