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

Это видео было создано для первой Летней математической выставки. Посмотрите и другие интересные видео там! https://www.3blue1brown.com/blog/some1 #some1 Patreon:   / polylog   Веб-сайт: https://polylog.cc Для создания этого видео мы использовали manim: https://docs.manim.community/en/stable/ Наше видео основано на следующей замечательной книге: Explaining Algorithms Using Metaphors авторы: Михал Форишек и Моника Стейнова вы можете купить её здесь: 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... Лицензия: добросовестное использование, надеюсь