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!
www.3blue1brown.com/blog/some1
#some1
Our Patreon: / polylog
To make this video, we used manim: 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: 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: people.csail.mit.edu/virgi/di...
-----------------------------------------------------------------------------------------------
Attributions:
The color palette: ethanschoonover.com/solarized/
Tree stump: creazilla.com/nodes/12939-tre...
License: creazilla.com/pages/11-creazi...
Drake meme: the guy in the photo is some singer: • Drake - Hotline Bling
License: fair use, hopefully
Ruler: pixabay.com/vectors/ruler-met...
License: pixabay.com/service/license/
Photo of Pál Erdős: commons.wikimedia.org/wiki/Fi...
License: creativecommons.org/licenses/...
A book: www.clker.com/cliparts/I/O/x/x...
License: www.clker.com/disclaimer.html
A tree: illustoon.com/?dl=383
License: illustoon.com/help.php
Bacteria tree adapted from: commons.wikimedia.org/wiki/Fi...
License: en.wikipedia.org/wiki/Public_...
Cover of the book Explaining Algorithms Using Metaphors: www.amazon.com/Explaining-Alg...
License: fair use, hopefully
1:55 "there are trees in biology" indeed there are 🗿🌳😂 great video though, love the gravity analogy!!
Indeed, trees are getting boring, we need fungus algorithms!
After watching I suddenly realized that I came up with this exact theorem when coding a maze generator and solver, I used it to find the longest path in the maze. I am very pleased to learn that my solution was exactly right.
Please have my children
I don't want them
@@deadsi bro
It's a trip that a maze is a tree of empty spaces. Thanks!
congratz, sir
The physical example was really enlightening. you're literally unfolding the hanger structure, making it longer
Thank you so much for this video! :D I've seen many some1 vids, and this one's my favourite! The real-life representation with the rope and beads really sold it :D
Nice explanation, nice embedding.
This video is so cool, I have no knowledge about math and algorithms and it was mind-blowing and awesome to follow.
the physical demonstration was so cool!
I paused the video and came up with my own proof. Designate a random node to be the root and keep it at the top. Suppose we find the "inverse depth" of every node: this is the depth of the subtree under each node. For example, the inverse depth of the root itself is just the depth of the tree, which is one more than the max of the inverse depths of all the root's children. Every path in the tree between two nodes first goes up to their shared parent node and then down to the second node. Let A and B be the two child nodes of this parent nodes which the path passes through. Then, the length of the longest possible path passing through A and B is the sum of their inverse depths plus one more for the parent node. So, really we are seeking to maximize the sum of two inverse depths of sister nodes. To find the diameter, one can imagine going through the tree layer by layer from the bottom up and finding the two nodes with the first and second highest inverse depths. If these two nodes are sister nodes, then this is a possibility, and we compare with the maximum length found so far to update the maximum. Now, here is why the algorithm in the video works: all the nodes in the path from the root node to the node furthest from it will have the highest inverse depth in their depth layer. So, at least one of the two nodes of a possible diameter must be the one which is furthest from the root. Knowing that this node has to be one of the endpoints of the diameter, one can just find the farthest node from this one and we are done.
First of all, thanks for watching so closely and digging deeper! I'm reading your proof and I'm not sure if I understand it correctly. From what I understand, in the first part you describe a different O(n) algorithm for computing the diameter, and then use it to analyze the "magical" algorithm. What I'm having trouble with is this part: "all the nodes in the path from the root node to the node furthest from it will have the highest inverse depth in their depth layer. So, at least one of the two nodes of a possible diameter must be the one which is furthest from the root." The two statements are both true but it seems to me the second doesn't follow from the first. Because even if a vertex has the highest inverse depth in the layer, what if it doesn't have any sister nodes? Then (perhaps) it could turn out that two different nodes that *are* siblings will have a higher sum. Or am I misunderstanding the proof? -Vaclav V
@@PolylogCS Sorry, I don't think I was clear enough. It may be possible at some depth layer that two nodes which are siblings have a higher sum although neither are that with the highest inverse depth. However, if we go enough layers up, there is some layer where a pair of siblings, one of which has the highest inverse depth, has a higher sum than the two nodes which we found originally. To prove this, note that if we trace the parents of the node with the highest inverse depth and the parent of the two siblings which summed to the highest number, they must meet up at some point. The two daughters of this parent node are the sister nodes with higher sum than the two nodes we had originally. Therefore, for every pair of siblings which does not contain the node of the highest inverse depth in the layer, there is another pair higher in the tree with a higher sum which does contain the node of the highest inverse depth in its layer. So, we only need to consider pairs which include the node of the highest inverse depth in that layer.
@@uy-ge3dm Got it, I think that works. Nice proof, it's always satisfying to have multiple ways of looking at the same problem.
I was confused on first minutes, i thought you create algorithm to calculate a diameter of real trunk 😅
Lol same
Excellent explanation with beads at 08:19
Great lecture!
For the odd diameter tree, the number of diameters is just l*r where l and r are the multiplicities of the left and right nodes. (ie do a breadth first, count how many nodes are at max distance on each half of the tree.) for an even diameter tree, you have a single central node. Let s be the list of counts of maximum distance nodes. So len(s)==degree of central node. then the number of diameters is (sum(s)**2-sum(s**2))/2 . Thus there is a linear algorithm for the number of diameters a tree has. And the number of diameters is at most N**2
That's right! I like the concise formula for the even-diameter case. -VV
great video! i'm just commenting to increase viewer engagement so youtube gives me more videos like this
Zdravim Českych kamaratov :) mate parádne vidka chalani, TOP.
side question: who is the composer of the background music?
This is awesome Love how you propagate Any chance you can link to the visualization tools you used ? (Python?)
Hi, glad you liked the video! We used Manim, a tool originally created by 3blue1brown and now maintained by a wider community: github.com/ManimCommunity/manim
beautiful!
what is the algorithm for longest path in directed weighted graph though? I tried just inverting the weights and using a star, no luck.
watching this, I realized that there is another way of explaining the mechanism behind that algorithm which might be even more intuitive: any node at maximum distance from a is going to be a node with only one neighbor. if it had multiple neighbors, they would be further from a than the node at maximum distance from a. since there is exactly one way to get from a given node to any other node, every node with only one neighbor is on the end of at least one diameter of the tree. as such, repeating the breadth-first search from a node which you know to be on one end of a diameter will tell you the length of that diameter, and since the first search gave you a node on one end of such a diameter, it works.
I don't think your logic is quite right. It is true that every diameter has solitary nodes at each end but that doesn't mean all solitary nodes are the ends of a diameter.
@@Danicker ah, good point. however, I am pretty sure that any solitary node that is of maximum distance from our starting node, however, will still be the end of a diameter.
He might be on to something.
Дуже гарна анімація
Are you an ETH student? :-) Hello from an ETH alumnus. :-D
"You may be surprized taht there are trees even in biology" NO WAAAY
those animations are freaking awesome how do you do that sir
www.manim.community/
What song is in the video?
Dear developer, whenever you think "tree", 90% of the time, you actually mean directed acyclic graph (multiple paths are allowed, but none leading back to their start).
Nice
Cool.
Who else took the thumbnail seriously but was pleasantly surprised
I did not understand the proof. You used the words "left side" and "right side" but they are defined only because you are already showing a diameter. What are the "left side" and the "top path" at 12:18 when the tree is still "folded"?
1:25 this confused me because of the "this" seemingly referring to what it was before you cut the edge, when you actually meant what happens after
Thanks for the feedback!
You found all of the longest paths.
Can't we just take any node with just one vertex and find its distance from every other node with just one vertex and the longest path will be the diameter of the tree, right ?
A node with 1 vertex is called a "leaf". There can be leaves which are close to the center of the tree, and as such, will have a shorter length to all other nodes
O \ O \ O --- O
There are times where you are changing subjects verbally but the visualization hasn't changed. That is pretty confusing for me personally, not sure if others agree.
1:57 "... you may be surprised to learn that there are trees even in biology ..." Nope , not really. I mean they are literally called 'trees'
exactly ;)
Thatsthejoke.png
#WaveDecompressionCombinatorics
Is there a name for this algorithm?
Not as far as I know
Thanks but I still don't know how thick this pine tree is
"and therefore, triangle"