Blossom algorithm: Difference between revisions

Revision as of 21:32, 5 September 2016

Revision as of 21:32, 5 September 2016

Line 68:

Given ''G'' = (''V'', ''E'') and a matching ''M'' of ''G'', a ''[[blossom (graph theory)|blossom]]'' ''B'' is a cycle in ''G'' consisting of ''2k + 1'' edges of which exactly ''k'' belong to ''M'', and where one of the vertices ''v'' of the cycle (the ''base'') is such that there exists an alternating path of even length (the ''stem'') from ''v'' to an exposed vertex ''w''.

We defineDefine the '''contracted graph''' ''G’'' as the graph obtained from ''G'' by [[edge contraction|contracting]] every edge of ''B'', and define the '''contracted matching''' ''M’'' as the matching of ''G’'' corresponding to ''M''.

[[File:Edmonds blossom.svg|500px|alt=Example of a blossom]]

}}</ref> that ''G’'' has an ''M’''-augmenting path [[if and only if|iff]] ''G'' has an ''M''-augmenting path, and that any ''M’''-augmenting path ''P’'' in ''G’'' can be '''lifted''' to an ''M''-augmenting path in ''G'' by undoing the contraction by ''B'' so that the segment of ''P’'' (if any) traversing through ''v_B'' is replaced by an appropriate segment traversing through ''B''.<ref Inname more= detail:"tarjan notes">{{citation

It can be shown<ref name = "tarjan notes">{{citation

| author = Tarjan, Robert

| contribution = Sketchy Notes on Edmonds' Incredible Shrinking Blossom Algorithm for General Matching

| title = Course Notes, Department of Computer Science, Princeton University

| url = http://www.cs.dartmouth.edu/~ac/Teach/CS105-Winter05/Handouts/tarjan-blossom.pdf

}}</ref> In more detail:

}}</ref> that ''G’'' has an ''M’''-augmenting path [[if and only if|iff]] ''G'' has an ''M''-augmenting path, and that any ''M’''-augmenting path ''P’'' in ''G’'' can be '''lifted''' to an ''M''-augmenting path in ''G'' by undoing the contraction by ''B'' so that the segment of ''P’'' (if any) traversing through ''v_B'' is replaced by an appropriate segment traversing through ''B''. In more detail:

* if ''P’'' traverses through a segment ''u → v_B → w'' in ''G’'', then this segment is replaced with the segment ''u → ( u’ → ... → w’ ) → w'' in ''G'', where blossom vertices ''u’'' and ''w’'' and the side of ''B'', ''( u’ → ... → w’ )'', going from ''u’'' to ''w’'' are chosen to ensure that the new path is still alternating (''u’'' is exposed with respect to <math>M \cap B</math>, <math>\{ w', w \} \in E \setminus M</math>).