StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>All trees contain no cycles. By definition, a tree is an cycle-free, connected graph. If there is one vertex, the answer is trivial. So assume there are at least two vertices.</p> <p>Let <em>u</em> and <em>v</em> be two vertices such that their distance <em>d</em> (<em>u</em>, <em>v</em>) is maximum. It should be easy to see that if one selects a vertex along a shortest <em>uv</em> path to be the root, the depth will be at least <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2). It should also be noted that if one selects a vertex to be the root not on that path, the depth will be greater than <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2).</p> <p>Suppose that we have chosen the root <em>r</em> to be the middle vertex along a minimum <em>uv</em> path such that <em>d</em> (<em>u</em>, <em>r</em>) = <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2) and <em>d</em> (<em>r</em>, <em>v</em>) ≤ <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2). If there were another vertex, <em>w</em>, such that <em>d</em> (<em>r</em>, <em>w</em>) > <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2), we would have <em>d</em> (<em>u</em>, <em>r</em>) < <em>d</em> (<em>w</em>, <em>r</em>) and then, because there is only one path between any two distinct vertices in a tree, we have <em>d</em> (<em>u</em>, <em>v</em>) = <em>d</em> (<em>u</em>, <em>r</em>) + <em>d</em> (<em>r</em>, <em>v</em>) < <em>d</em> (<em>u</em>, <em>r</em>) + <em>d</em> (<em>r</em>, <em>w</em>) = <em>d</em> (<em>u</em>, <em>w</em>), which contradicts that <em>u</em> and <em>v</em> have the greatest distance. So now the depth, given <em>r</em> as the root, is <em>ceiling</em> (<em>d</em> (<em>u</em>, <em>v</em>) / 2).</p> <p>So we need to find the two vertices with the largest distance. Once we do that, we can use a shortest path-finding algorithm for <em>uv</em>, note the length, and traverse half-way along said path and use that middle vertex as the root.</p> <p>How do we find those vertices? Pick a vertex <em>w</em> and place it in a queue. While the queue is non-empty add the neighbors of the next vertex in the queue to the end of the queue. When the queue is empty, take note of the most recently removed vertex. This will be <em>u</em>. Perform the procedure again and you will have <em>v</em>.</p> <p>Why does this work? The above algorithm finds a furthest away vertex from <em>w</em>. If <em>w</em> happens to be <em>u</em> or <em>v</em>, the algorithm clearly finds <em>v</em> or <em>u</em>, respectively. So suppose <em>w</em> is neither <em>u</em> nor <em>v</em>. If the algorithm found a <em>u</em> or <em>v</em> in the first pass, again, it will work (for it will find the other in the second pass), so assume, by way of contradiction, that after the first pass it found <em>x</em> such that it is not the end of a maximum path for the tree. From the triangle inequality we have <em>d</em> (<em>u</em>, <em>v</em>) ≤ <em>d</em> (<em>u</em>, <em>w</em>) + <em>d</em> (<em>w</em>, <em>v</em>) and <em>d</em> (<em>v</em>, <em>x</em>) ≤ <em>d</em> (<em>v</em>, <em>w</em>) + <em>d</em> (<em>w</em>, <em>x</em>). Subtracting the second from the first we have <em>d</em> (<em>u</em>, <em>v</em>) - <em>d</em> (<em>v</em>, <em>x</em>) ≤ <em>d</em> (<em>u</em>, <em>w</em>) - <em>d</em> (<em>w</em>, <em>x</em>). We can then rearrange that to <em>d</em> (<em>u</em>, <em>v</em>) + <em>d</em> (<em>w</em>, <em>x</em>) ≤ <em>d</em> (<em>u</em>, <em>w</em>) + <em>d</em> (<em>v</em>, <em>x</em>). Since <em>d</em> (<em>w</em>, <em>u</em>) ≤ <em>d</em> (<em>w</em>, <em>x</em>) (<em>x</em> is the end of a maximum path from <em>w</em>; <em>wu</em> cannot exceed <em>wx</em>) and <em>d</em> (<em>v</em>, <em>x</em>) < <em>d</em> (<em>u</em>, <em>v</em>) (<em>x</em> is not the end of a maximum path), we can strengthen the inequality to <em>d</em> (<em>u</em>, <em>v</em>) + <em>d</em> (<em>w</em>, <em>x</em>) < <em>d</em> (<em>u</em>, <em>v</em>) + <em>d</em> (<em>w</em>, <em>x</em>). That's not possible, though, so <em>x</em> must be at the end of a maximum path.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload