How to Use Beads and Strings to Find the Diameter of a Tree

This video was made for the Summer of Math Exposition 1. Check out other cool videos there! https://www.3blue1brown.com/blog/some1 #some1 Patreon:   / polylog   Website: https://polylog.cc To make this video, we used manim: https://docs.manim.community/en/stable/ Our video is based on the following great book: Explaining Algorithms Using Metaphors by Michal Forišek and Monika Steinová you can buy it here: https://www.springerprofessional.de/e... 0:00 Intro 0:40 Trees 6:19 The algorithm 7:43 Why it works ----------------------------------------------------------------------------------------------- Fill in the gaps: It is a good exercise to fill in the missing gaps in the proof sketch that we gave in the video, where we focused on a particular tree instead of analyzing our algorithm in full generality. For example: we started by observing that if we hang a tree by its longest path, its nodes are contained in a triangle. How is this fact used in the actual proof? Also: it can help with understanding the algorithm to consider the case when the tree is simply a path. What else follows from the triangle picture: The one or two nodes that are in the middle of the top edge of our triangle (see the end of the video) are also called the center of the tree. They have the following properties (formally, you would use one of these to define the center of the tree): The center is in the middle of any longest path of the tree Leaves are the nodes with just one connection. If you repeatedly remove leaves from the tree (in each step, you remove all current leaves, in the next step the nodes that became leaves, and so on), the center is the last remaining node(s) before the whole tree is removed. Eccentricity of a node is the distance to the farthest node from it. The center is the node(s) with minimum eccentricity. Fun Riddles: Compute eccentricities of all nodes of a tree with an algorithm with linear time complexity (=number of steps at most some constant times number of nodes) Compute the number of longest paths in a tree with an algorithm with linear time complexity More Connections: A more general question is: what is the diameter of a general network (there, diameter = longest distance between two nodes in it). This problem can be again solved by a naive algorithm that iterates over all nodes and finds the farthest node from each one. There is a substantially faster algorithm that uses similar ideas to those we saw in the video. The downside is that the algorithm is only approximate. If the true answer is D, it returns some number D’ that satisfies 2D/3 ≤ D’ ≤ D. That may seem unsatisfactory, but we know that if there is a nontrivial algorithm with at least slightly better approximation than the one above, something similar to P=NP happens (whether P=NP is the biggest problem in computer science and is considered unlikely to be true). The relevant paper: https://people.csail.mit.edu/virgi/di... ----------------------------------------------------------------------------------------------- Attributions: The color palette: https://ethanschoonover.com/solarized/ Tree stump: https://creazilla.com/nodes/12939-tre... License: https://creazilla.com/pages/11-creazi... Drake meme: the guy in the photo is some singer:    • Drake - Hotline Bling   License: fair use, hopefully Ruler: https://pixabay.com/vectors/ruler-met... License: https://pixabay.com/service/license/ Photo of Pál Erdős: https://commons.wikimedia.org/wiki/Fi... License: https://creativecommons.org/licenses/... A book: http://www.clker.com/cliparts/I/O/x/x... License: http://www.clker.com/disclaimer.html A tree: https://illustoon.com/?dl=383 License: https://illustoon.com/help.php Bacteria tree adapted from: https://commons.wikimedia.org/wiki/Fi... License: https://en.wikipedia.org/wiki/Public_... Cover of the book Explaining Algorithms Using Metaphors: https://www.amazon.com/Explaining-Alg... License: fair use, hopefully