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.

Blossom definition problem

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]

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)[reply]

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)[reply]

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)[reply]

I tried to account for the problem you reported and to reformulate the article. Hopefully it is correct now. --a3_nm (talk) 15:26, 2 June 2012 (UTC)[reply]

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)[reply]

I updated the diagrams. Does this problem still occur? --a3_nm (talk) 15:26, 2 June 2012 (UTC)[reply]

Can someone check, please?

I reverted an edit because it had changed "if and only if" to the incorrect spelling "iff".[1] Then I thought I'd better check in case the edit content was correct and just had a typo.

Daiyuda's edit: "Matching M is not maximum iff there exists an M-augmenting path in G."
My revert: "Matching M is not maximum if and only if there exists an M-augmenting path in G."
Online source:[2] "M is not a maximum matching if and only if there exists an augmenting path with respect to M."

Maybe that quote is referring to something different. But that sentence is the only match I found for "if and only if". Girlwithgreeneyes (talk) 23:04, 9 April 2012 (UTC)[reply]