Как использовать бусины и нитки, чтобы определить диаметр дерева

Это видео было снято для выставки Summer of Math Exposition 1. Посмотрите другие интересные видео там! https://www.3blue1brown.com/blog/some1
#some1

Наш Patreon:   / polylog  

Для создания этого видео мы использовали manim: https://docs.manim.community/en/stable/

Наше видео основано на следующей замечательной книге: «Объяснение алгоритмов с помощью метафор» Михала Форишека и Моники Штейновой. Купить её можно здесь: https://www.springerprofessional.de/e...

0:00 Вступление
0:40 Деревья
6:19 Алгоритм
7:43 Почему это работает

-----------------------------------------------------------------------------------------------

Заполните пробелы:

Это хорошее упражнение для заполнения пробелов в наброске доказательства, который мы В видео мы сосредоточились на конкретном дереве, а не на анализе нашего алгоритма в полном объёме. Например, мы начали с наблюдения, что если подвесить дерево за самый длинный путь, его узлы попадут в треугольник. Как этот факт используется в доказательстве?

Кроме того, для понимания алгоритма может быть полезно рассмотреть случай, когда дерево представляет собой просто путь.

Что ещё следует из рисунка с треугольником:

Один или два узла, находящиеся в середине верхнего ребра нашего треугольника (см. конец видео), также называются центром дерева. Они обладают следующими свойствами (формально, для определения центра дерева можно использовать одно из них):

Центр находится в середине любого самого длинного пути дерева.
Листья — это узлы, имеющие только одну связь. Если многократно удалять листья из дерева (на каждом шаге удаляются все текущие листья, на следующем шаге — узлы, ставшие листьями, и так далее), центром будет последний оставшийся узел (узлы) перед удалением всего дерева. - Эксцентриситет узла — это расстояние до самого удалённого от него узла. Центр — это узел(ы) с минимальным эксцентриситетом.

Забавные загадки:

Вычислите эксцентриситет всех узлов дерева с помощью алгоритма с линейной временной сложностью (= количеству шагов, не превышающему некоторую константу, умноженную на количество узлов).
Вычислите количество самых длинных путей в дереве с помощью алгоритма с линейной временной сложностью.

Ещё связи:

Более общий вопрос: чему равен диаметр сети в общем случае (здесь диаметр = наибольшее расстояние между двумя узлами в ней). Эту задачу можно решить с помощью простого алгоритма, который перебирает все узлы и находит самый удалённый от каждого из них узел.
Существует значительно более быстрый алгоритм, использующий идеи, похожие на те, что мы видели в видео. Недостатком является то, что алгоритм работает лишь приблизительно. Если истинный ответ — D, возвращается некоторое число D’, удовлетворяющее условию 2D/3 ≤ D’ ≤ D.
Это может показаться неудовлетворительным, но мы знаем, что если существует нетривиальный алгоритм с хотя бы немного лучшим приближением, чем приведённый выше, происходит нечто похожее на P=NP (независимо от того, является ли P=NP самой большой проблемой в информатике и считается ли оно маловероятным). Соответствующая статья: https://people.csail.mit.edu/virgi/di...

-----------------------------------------------------------------------------------------------

Указание авторства:

Цветовая палитра: https://ethanschoonover.com/solarized/

Пень: https://creazilla.com/nodes/12939-tre...
Лицензия: https://creazilla.com/pages/11-creazi...

Мем про Дрейка: парень на фото — какой-то певец:    • Drake - Hotline Bling  
Лицензия: надеюсь, добросовестное использование

Линейка: https://pixabay.com/vectors/ruler-met...
Лицензия: https://pixabay.com/service/license/

Фотография Пала Эрдеша: https://commons.wikimedia.org/wiki/Fi...
Лицензия: https://creativecommons.org/licenses/....

Книга: http://www.clker.com/cliparts/I/O/x/x....
Лицензия: http://www.clker.com/disclaimer.html.

Дерево: https://illustoon.com/?dl=383
Лицензия: https://illustoon.com/help.php.

Дерево бактерий адаптировано из: https://commons.wikimedia.org/wiki/Fi....
Лицензия: https://en.wikipedia.org/wiki/Public_...

Обложка книги «Объяснение алгоритмов с помощью метафор»: https://www.amazon.com/Explaining-Alg...
Лицензия: добросовестное использование, надеемся.