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/tree/master/06-edmonds-blossom

Music: Maisie Dreamer by Blue Dot Sessions: https://app.sessions.blue/browse/track/31458

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: Patreon (if you'd like to support me): https://www.patreon.com/TomasSlama Website (for other things I'm up to): https://slama.dev/

[EN] Proofs: https://web.stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

• 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/kombinatorika-a-grafy-ii/

[EN] Sketchy Notes on Edmonds’ Incredible Shrinking Blossom http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf

[EN] Amy Shoemaker and Sagar Vare's report on the blossom algorithm: https://web.stanford.edu/~rezab/classes/cme323/S16/projects_reports/shoemaker_vare.pdf

[EN] Blossom algorithm on Wikipedia: https://en.wikipedia.org/wiki/Blossom_algorithm ... https://www.youtube.com/watch?v=3roPs1Bvg1Q