Talk:Blossom algorithm

Mathematics Start‑class Low‑priority

	Mathematics portal This article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.MathematicsWikipedia:WikiProject MathematicsTemplate:WikiProject Mathematicsmathematics
Start	This article has been rated as Start-class on Wikipedia's content assessment scale.
Low	This article has been rated as Low-priority on the project's priority scale.

i think the definition of blossom here is slightly incorrect. a blossom is not just a cycle of size 2k+1 that contains exactly k matched edges. if it were that, then, contrary to the main theorem about blossoms, the following graph G would contain a blossom B and an augmenting path P even though after contracting B, the resulting graph G' does _not_ contain an augmenting path:

    a
    |
    b
   / \
c-d---e-f

(here the matching is M = {ab, de}, the fake blossom B = {bd, de, eb}, and the augmenting path P = {cd, de, ef}. G' after contracting B has no augmenting path.) rather, i think a blossom is also required to have connected to its base (b in this case) a simple path, vertex disjoint with B except for the base vertex, with an even number of edges, beginning with a free vertex, and alternating between unmatched and matched edges.

does anyone want to weigh in on this? --Unique-k-sat (talk) 05:49, 19 October 2009 (UTC)[reply]