We prove the correctness of the search for the diameter of the tree
Once in the standings, I got the next task. Come up with an algorithm that finds two vertices of the tree with the maximum distance from each other, and prove its correctness. At that moment, I basically did not know that trees have a diameter, a radius, and many other things. After the test, a friend enlightened me, telling me what the algorithm was, but without proof. It was with the question of evidence that my head was clogged for a long time. After reading a few articles, it became clear that the material does not settle down until I myself can explain everything on my fingers (maybe the reader will like it). Let's move from demagogy to the point.
The diameter of the tree is the maximum distance between two vertices in the tree. The search algorithm consists of two launches of BFS. The first goes from an arbitrary top of the tree; during the traversal, the distances from the current top to all others are recorded. Then the most distant is selected from them. From it, the second launch of BFS is done. There are new distances. The maximum among them will be the diameter.
Why does this seemingly simple algorithm work correctly?
To avoid the pitfalls in the proof, we will immediately discuss the case of a tree from one vertex and two vertices. If there is one vertex, then we have no edges, the first BFS will inform that the starting vertex has the maximum depth, the second - also. In fact, this is the case, the algorithm will work correctly. If there are two vertices, then the first traversal will come to the second vertex, and the second - to the starting one, which is correct for this case.
')
First, we understand that the desired distance is the distance between two sheets. In fact, let the vertex at the end of the found maximal path not be a leaf. At the same time, we cannot increase the desired distance by assumption. However, this means that BFS did not visit the vertices “located behind” the current one, which contradicts the correctness of BFS. It turns out that both the vertices found are leaves. Perfectly.
We hang our tree by the vertex v , from which we launch the first traversal.
Consider a separate case where the vertex v is itself a leaf. If it is the first end of the diameter, then it is obvious that the first BFS will find the second end, and the second will return to the starting vertex. Otherwise, the diameter will not pass through v and will also bend over, since it cannot contain more than two leaves.
Suppose we found a diameter and two vertices corresponding to it. Find the LCA of these vertices a and b , let's call this vertex c . It is obvious that D = d [a, c] + d [c, b] . In fact, the diameter is the sum of the two deepest subtrees of a certain vertex, if it belongs to the longest path. The diameter of a tree is the maximum diameter among all subtrees. The first detour in width will give us the maximum peak in depth (as we hung on the starting peak). Denote the vertex at the end of the found path w . Let us prove that w will belong to the desired longest path. Let the diameter “bends” at the vertex c (it will “bend” because it connects two leaves, and the tree is suspended by the vertex v , which is not a leaf). Let the vertex w belong to one of the subtrees of the vertex c . Then simply replace some part of the path (c, x) , where x is one of the ends, with (c, w). d [c, x] <d [c, w]. We have improved the answer. Hence, the original path was not a diameter. If w is an ancestor of c , then w is not a leaf, so this case does not exist. If w is somewhere in another subtree, then let e = LCA (c, w) . d [w, e] - the maximum depth of the subtree e . Then, since e is the ancestor of c , then d [x, e]> d [x, c] . d [w, e]> d [y, e]> d [y, c] . Therefore, D0 = d [x, c] + d [y, c] <d [x, e] + d [w, e] = D. Hence, the original diameter was found incorrectly and the vertex w belongs to the diameter.
Note:
In this part of the proof, we used the property that the leaf w has the greatest depth in any subtree of this tree to which w belongs. We prove by induction. Base - one sheet w . Obviously, the statement is true. Suppose that for some subtree this is also true, then let us go up a level. Suppose there is a vertex whose depth in the current subtree is greater than that of w . We call the current vertex a , the vertex with the assumed greater depth x , the root of the tree v .
d [v, x] = d [v, a] + d [a, x];
d [v, w] = d [v, a] + d [a, w];
d [v, x] <d [v, w] due to the correctness of the BFS operation;
d [a, x]> d [a, w] by assumption;
As a result, we obtain a contradiction. Therefore, the vertex w has the greatest depth in any subtree.
We obtain that the vertex w belongs to the diameter and is also one of its ends. Then it is obvious that it remains only to find the vertex most distant from w , which is what the second BFS does.
When writing the article materials were used:
neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_ % D0% BD% D0% B0_% D0% B4% D0% B5% D1% 80% D0% B5% D0% B2% D1% 8C% D1% 8F% D1% 85
The diameter of the tree is the maximum distance between two vertices in the tree. The search algorithm consists of two launches of BFS. The first goes from an arbitrary top of the tree; during the traversal, the distances from the current top to all others are recorded. Then the most distant is selected from them. From it, the second launch of BFS is done. There are new distances. The maximum among them will be the diameter.
Why does this seemingly simple algorithm work correctly?
To avoid the pitfalls in the proof, we will immediately discuss the case of a tree from one vertex and two vertices. If there is one vertex, then we have no edges, the first BFS will inform that the starting vertex has the maximum depth, the second - also. In fact, this is the case, the algorithm will work correctly. If there are two vertices, then the first traversal will come to the second vertex, and the second - to the starting one, which is correct for this case.
')
First, we understand that the desired distance is the distance between two sheets. In fact, let the vertex at the end of the found maximal path not be a leaf. At the same time, we cannot increase the desired distance by assumption. However, this means that BFS did not visit the vertices “located behind” the current one, which contradicts the correctness of BFS. It turns out that both the vertices found are leaves. Perfectly.
We hang our tree by the vertex v , from which we launch the first traversal.
Consider a separate case where the vertex v is itself a leaf. If it is the first end of the diameter, then it is obvious that the first BFS will find the second end, and the second will return to the starting vertex. Otherwise, the diameter will not pass through v and will also bend over, since it cannot contain more than two leaves.
Suppose we found a diameter and two vertices corresponding to it. Find the LCA of these vertices a and b , let's call this vertex c . It is obvious that D = d [a, c] + d [c, b] . In fact, the diameter is the sum of the two deepest subtrees of a certain vertex, if it belongs to the longest path. The diameter of a tree is the maximum diameter among all subtrees. The first detour in width will give us the maximum peak in depth (as we hung on the starting peak). Denote the vertex at the end of the found path w . Let us prove that w will belong to the desired longest path. Let the diameter “bends” at the vertex c (it will “bend” because it connects two leaves, and the tree is suspended by the vertex v , which is not a leaf). Let the vertex w belong to one of the subtrees of the vertex c . Then simply replace some part of the path (c, x) , where x is one of the ends, with (c, w). d [c, x] <d [c, w]. We have improved the answer. Hence, the original path was not a diameter. If w is an ancestor of c , then w is not a leaf, so this case does not exist. If w is somewhere in another subtree, then let e = LCA (c, w) . d [w, e] - the maximum depth of the subtree e . Then, since e is the ancestor of c , then d [x, e]> d [x, c] . d [w, e]> d [y, e]> d [y, c] . Therefore, D0 = d [x, c] + d [y, c] <d [x, e] + d [w, e] = D. Hence, the original diameter was found incorrectly and the vertex w belongs to the diameter.
Note:
In this part of the proof, we used the property that the leaf w has the greatest depth in any subtree of this tree to which w belongs. We prove by induction. Base - one sheet w . Obviously, the statement is true. Suppose that for some subtree this is also true, then let us go up a level. Suppose there is a vertex whose depth in the current subtree is greater than that of w . We call the current vertex a , the vertex with the assumed greater depth x , the root of the tree v .
d [v, x] = d [v, a] + d [a, x];
d [v, w] = d [v, a] + d [a, w];
d [v, x] <d [v, w] due to the correctness of the BFS operation;
d [a, x]> d [a, w] by assumption;
As a result, we obtain a contradiction. Therefore, the vertex w has the greatest depth in any subtree.
We obtain that the vertex w belongs to the diameter and is also one of its ends. Then it is obvious that it remains only to find the vertex most distant from w , which is what the second BFS does.
When writing the article materials were used:
neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D1%8B_ % D0% BD% D0% B0_% D0% B4% D0% B5% D1% 80% D0% B5% D0% B2% D1% 8C% D1% 8F% D1% 85
Source: https://habr.com/ru/post/305912/
All Articles