⚠ Switch to EXCALIDRAW VIEW in the MORE OPTIONS menu of this document. ⚠ You can decompress Drawing data with the command palette: ‘Decompress current Excalidraw file’. For more info check in plugin settings under ‘Saving’
Excalidraw Data
Text Elements
Graph the Algorithm is performed on.
Directed Graph
Red: Exposed Vertex
An arrow pointing back into the Node represents an empty path.
Orange Arrow: represents the imaginary edge to the neighbor.
G with the first edge in the matching.
The corresponding directed Graph
Green: A vertex with an exposed neighbor.
The red edges are in the matching.
Blue: A vertex with no exposed neighbors.
A path with a length of 1. I have drawn green arrow like this to show which vertices of G are in the path.
The last path was actually a blossom.
Therefore we change G to this.
Also a blossom.
Here we do not choose the start vertex as the neighbor and therefore is this path not a blossom.
Therefore we flip the matching in the path.
There are no exposed vertices. Therefore there is no shortest path. Hence the matching is maximum.
We expand the blossoms recursively.
Also already a maximum matching.
All blossoms are expanded and there is no path. Therefore this is a maximum matching of G.