Talk:Blossom algorithm

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)

yes, you are right! actually, tarjan's notes (that is where the theorem was taken from) also have some additional conditions on what blossoms qualify for the shrinking theorem. i think there are two ways how this could be fixed. do literature search and see how blossoms are defined in other sources. if they are still defined as in the wiki article, then the theorem in the main article has to be updated to state the additional conditions under which the theorem holds. if cycles have to have "stems" in order to be called blossoms, then only the definition of blossoms has to be changed to reflect this. that said, i believe the algorithm is still correct and so only either the theorem or the definition of blossoms have to be changed. 128.148.33.99 (talk) 21:44, 14 July 2010 (UTC)

One source that points this out and gives a correct version of the algorithm is Jungnickel Graphs, Networks and Algorithms. --46.253.62.108 (talk) 05:06, 7 September 2011 (UTC)

I made a correct description of the algorithm in de.WP and also provided a correct example. de:Paarung_(Graphentheorie)#Algorithmus_von_Edmonds. Not sure when or if I will find time & leisure to translate it. --goiken 17:24, 12 September 2011 (UTC)

Blossom Diagram & Augmenting path

In the first blossom diagram, the augmenting path that is shown starts at u. Since u is adjacent to an edge in the matching, that isn't an augmenting path, right? Zabwung (talk) 00:58, 6 July 2011 (UTC)