Blossom algorithm: Difference between revisions

Revision as of 19:07, 30 June 2017

Revision as of 19:20, 30 June 2017

Line 32:

==Augmenting paths==

Given ''G'' = (''V'', ''E'') and a matching ''M'' of ''G'', a vertex ''v'' is '''exposed''' if no edge of ''M'' is incident with ''v''. A path in ''G'' is an '''alternating path''', if its edges are alternately not in ''M'' and in ''M'' (or in ''M'' and not in ''M''). An '''augmenting path''' ''P'' is an alternating path that starts and ends at two distinct exposed vertices. (noteNote that suchnumber aof pathunmatched mustedges havein an oddaugmenting path is greater by one than the number of matched edges), and hence the total number of edges in an augmenting path is odd. A '''matching augmentation''' along an augmenting path ''P'' is the operation of replacing ''M'' with a new matching <math>M_1 = M \oplus P = ( M \setminus P ) \cup ( P \setminus M )</math>.

[[File:Edmonds augmenting path.svg|500px|alt=Augmentation along a path]]