Talk:Blossom algorithm: Difference between revisions
No edit summary |
No edit summary |
||
Line 24: | Line 24: | ||
[[Special:Contributions/128.148.33.99|128.148.33.99]] ([[User talk:128.148.33.99|talk]]) 21:44, 14 July 2010 (UTC) |
[[Special:Contributions/128.148.33.99|128.148.33.99]] ([[User talk: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''. --[[Special:Contributions/46.253.62.108|46.253.62.108]] ([[User talk:46.253.62.108|talk]]) 05:06, 7 September 2011 (UTC) |
:One source that points this out and gives a correct version of the algorithm is Jungnickel ''Graphs, Networks and Algorithms''. --[[Special:Contributions/46.253.62.108|46.253.62.108]] ([[User talk: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. [[Paarung_(Graphentheorie)#Algorithmus_von_Edmonds]]. Not sure when or if I will find time & leisure to translate it. --[[user:0g1o2i3k4e5n6|goiken]] 17:24, 12 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. --[[user:0g1o2i3k4e5n6|goiken]] 17:24, 12 September 2011 (UTC) |
||
===Blossom Diagram & Augmenting path=== |
===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? [[User:Zabwung|Zabwung]] ([[User talk:Zabwung|talk]]) 00:58, 6 July 2011 (UTC) |
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? [[User:Zabwung|Zabwung]] ([[User talk:Zabwung|talk]]) 00:58, 6 July 2011 (UTC) |
Revision as of 17:25, 12 September 2011
{{WikiProject banner shell}}
to this page and add the quality rating to that template instead of this project banner. See WP:PIQA for details.![]() | Mathematics Start‑class Low‑priority | |||||||||
|
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)