Talk:Blossom algorithm: Difference between revisions

Revision as of 05:49, 19 October 2009

Revision as of 05:54, 19 October 2009

Line 3:

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:

<nowikipre>

a
a|

b
/ |\

c-d---e-f

b

</pre>

/ \

c-d-e-f

</nowiki>

(here the matching is M = {ab, de}, the fake blossom B = {bd, de, eb}, and the augmenting path P = {cd, de, ef}.