Revision as of 05:32, 12 December 2016 edit Omaramin1992 (talk \| contribs) 1 edit m Added how Blossoms are found in graphs. Tag: Visual edit ← Previous edit		Revision as of 04:27, 13 December 2016 edit undo Yobot (talk \| contribs) Bots 4,733,870 edits m →Blossoms and contractions: Removed invisible unicode characters + other fixes, replaced: → (2) using AWB Next edit →
Line 71: * Using DFS "Depth-First-Search", traverse the graph starting from an exposed or a free vertex. * Starting from that vertex, label it as an outer vertex "'''''o'''"''. * Alternate the labeling between vertices being inner "'''''i'''"'' and outer "'''''o'''"'' such that no two adjacent vertices have the same label. * If we end up with two adjacent vertices labeled as outer "'''''o'''"'' then we have a blossom. Define 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''.

Blossom algorithm: Difference between revisions