Алгоритм «цветок»

Обзор алгоритма Blossom для поиска максимального соответствия графам. ------------------ Расписание: 0:00 - Введение 0:41 - Определения 1:02 - Расширение путей 1:42 - Максимальное сопоставление деревьев 3:06 - Цветы 4:06 - Максимальное сопоставление графов общего типа 4:59 - Обзор 5:46 - Заключение ------------------ Исходный код: https://github.com/xiaoxiae/videos/tr... Музыка: Maisie Dreamer от Blue Dot Sessions: https://app.sessions.blue/browse/trac... Используемое программное обеспечение: Manim (анимация): https://github.com/ManimCommunity/manim/ Kdenlive (видео): https://kdenlive.org/en/ ffmpeg (видео): https://ffmpeg.org/ Vector Magic (изображения): https://vectormagic.com/ arecord (аудио): https://linux.die.net/man/1/arecord sox (аудио): http://sox.sourceforge.net/ Социальные сети: Веб-сайт (для других моих проектов): https://slama.dev/ Patreon (если вы хотите меня поддержать):   / ytoms   ------------------ [EN] Доказательства: https://web.stanford.edu/~rezab/class... граф имеет арифметическую прогрессию тогда и только тогда, когда паросочетание не является максимальным: теорема 2.4 граф имеет арифметическую прогрессию тогда и только тогда, когда сжатый граф имеет арифметическую прогрессию: теорема 2.9 [CZ] Мои заметки по лекции Мартина Коутецкого «Комбинаторика и графы»: https://slama.dev/lecture-notes/kombi... [EN] Краткие заметки о невероятном алгоритме «сжимающегося цветка» Эдмондса http://www.cs.dartmouth.edu/~ac/Teach... [EN] Отчет Эми Шумейкер и Сагара Варе об алгоритме «цветка»: https://web.stanford.edu/~rezab/class... [EN] Алгоритм «цветка» на Википедия: https://en.wikipedia.org/wiki/Blossom...