The Blossom Algorithm

An overview of the Blossom algorithm for maximum graph matching. ------------------ Timetable: 0:00 - Introduction 0:41 - Definitions 1:02 - Augmenting paths 1:42 - Maximum tree matching 3:06 - Blossoms 4:06 - Maximum general graph matching 4:59 - Overview 5:46 - Outro ------------------ Source code: https://github.com/xiaoxiae/videos/tr... Music: Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/trac... Software used: Manim (animations): https://github.com/ManimCommunity/manim/ Kdenlive (video): https://kdenlive.org/en/ ffmpeg (video): https://ffmpeg.org/ Vector Magic (images): https://vectormagic.com/ arecord (audio): https://linux.die.net/man/1/arecord sox (audio): http://sox.sourceforge.net/ Social media: Website (for other things I'm up to): https://slama.dev/ Patreon (if you'd like to support me):   / ytoms   ------------------ [EN] Proofs: https://web.stanford.edu/~rezab/class... graph has an a.p. if and only if the matching is not maximum: theorem 2.4 graph has an a.p. if and only if compressed graph has an a.p.: theorem 2.9 [CZ] My notes on Martin Koutecký's Combinatorics and Graphs lecture: https://slama.dev/lecture-notes/kombi... [EN] Sketchy Notes on Edmonds’ Incredible Shrinking Blossom http://www.cs.dartmouth.edu/~ac/Teach... [EN] Amy Shoemaker and Sagar Vare's report on the blossom algorithm: https://web.stanford.edu/~rezab/class... [EN] Blossom algorithm on Wikipedia: https://en.wikipedia.org/wiki/Blossom...