|
==Blossoms and contractions==
Given {{math|1=''G'' = (''V'', ''E'')}} and a matching ''{{mvar|M''}} of ''{{mvar|G''}}, a ''[[blossom (graph theory)|blossom]]'' ''{{mvar|B''}} is a cycle in ''{{mvar|G''}} consisting of {{math|2''k''2k + 1''}} edges of which exactly ''{{mvar|k''}} belong to ''{{mvar|M''}}, and where one of the vertices ''{{mvar|v''}} of the cycle (the ''base'') is such that there exists an alternating path of even length (the ''stem'') from ''{{mvar|v''}} to an exposed vertex ''{{mvar|w''}}.
'''''Finding Blossoms:'''''
* Traverse the graph starting from an exposed vertex.
* Starting from that vertex, label it as an outer vertex "''{{mvar|'''o'''"''}}.
* Alternate the labeling between vertices being inner "''{{mvar|'''i'''"''}} and outer "''{{mvar|'''o'''"''}} such that no two adjacent vertices have the same label.
* If we end up with two adjacent vertices labeled as outer "''{{mvar|'''o'''"''}} then we have an odd-length cycle and hence a blossom.
Define the '''contracted graph''' {{mvar|G''G’''}} as the graph obtained from ''{{mvar|G''}} by [[edge contraction|contracting]] every edge of ''{{mvar|B''}}, and define the '''contracted matching''' {{mvar|M''M’''}} as the matching of {{mvar|G''G’''}} corresponding to ''{{mvar|M''}}.
[[File:Edmonds blossom.svg|500px|alt=Example of a blossom]]
{{mvar|G''G’''}} has an {{mvar|M''M’''}}-augmenting path [[if and only if]] ''{{mvar|G''}} has an ''{{mvar|M''}}-augmenting path, and that any {{mvar|M''M’''}}-augmenting path {{mvar|P''P’''}} in {{mvar|G''G’''}} can be '''lifted''' to an ''{{mvar|M''}}-augmenting path in ''{{mvar|G''}} by undoing the contraction by ''{{mvar|B''}} so that the segment of {{mvar|P''P’''}} (if any) traversing through ''{{mvar|v<{{sub>|B</sub>''}}}} is replaced by an appropriate segment traversing through ''{{mvar|B''}}.<ref name = "tarjan notes">{{citation
| author = Tarjan, Robert
| contribution = Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching
}}</ref> In more detail:
* if {{mvar|P''P’''}} traverses through a segment {{math|''u'' → ''v<{{sub>|B</sub>}}'' → ''w''}} in {{mvar|G''G’''}}, then this segment is replaced with the segment {{math|''u'' → ( u’''u''' → ...… → w’''w' '' ) → ''w''}} in ''{{mvar|G''}}, where blossom vertices {{mvar|u''u’''}} and {{mvar|w''w’''}} and the side of ''{{mvar|B}}, {{math|( '',u' ''( u’ → ...… → w’''w' )'' )}}, going from {{mvar|u''u’''}} to {{mvar|w''w’''}} are chosen to ensure that the new path is still alternating ({{mvar|u''u’''}} is exposed with respect to <math>M \cap B</math>, <math>\{ w', w \} \in E \setminus M</math>).
[[File:Edmonds lifting path.svg|500px|alt=Path lifting when {{mvar|P''P’''}} traverses through ''{{mvar|v<{{sub>|B</sub>''}}}}, two cases depending on the direction we need to choose to reach ''{{mvar|v<{{sub>|B</sub>''}}}}]]
* if {{mvar|P''P’''}} has an endpoint ''{{mvar|v<{{sub>|B</sub>''}}}}, then the path segment {{math|''u'' → ''v<{{sub>|B</sub>}}''}} in {{mvar|G''G’''}} is replaced with the segment {{math|''u'' → ( u’''u' '' → ...… → v’''v' )'' )}} in ''{{mvar|G''}}, where blossom vertices {{mvar|u''u’''}} and {{mvar|v''v’''}} and the side of ''{{mvar|B''}}, {{math|( ''(u' u’'' → ...… → v’''v' )'' )}}, going from {{mvar|u''u’''}} to {{mvar|v''v’''}} are chosen to ensure that the path is alternating ({{mvar|v''v’''}} is exposed, <math>\{ u', u \} \in E \setminus M</math>).
[[File:Edmonds lifting end point.svg|500px|alt=Path lifting when {{mvar|P''P’''}} ends at ''{{mvar|v<{{sub>|B</sub>''}}}}, two cases depending on the direction we need to choose to reach ''{{mvar|v<{{sub>|B</sub>''}}}}]]
Thus blossoms can be contracted and search performed in the contracted graphs. This reduction is at the heart of Edmonds' algorithm.
| 