Content deleted Content added
m →Blossoms and contractions: Removed invisible unicode characters + other fixes, replaced: → (2) using AWB |
→Blossoms and contractions: Doesn't matter whether DFS or BFS - pseudocode later in the article specifies neither |
||
Line 69:
'''''Finding Blossoms:'''''
*
* 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 an odd-length cycle and hence 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''.
| |||