Talk:Matching
From Wikipedia, the free encyclopedia
There is something I miss on this page. It does not mention that there are both maximum cardinality and maximum value matching problems. I am not sure if these are the "correct" names. Maximum cardinality bipartite matching: All edges are worth equally much. Can be solved with Maximum flow by adding a super-source and a super-sink. Maximum value bipartite matching: Edges are not worth the same, and you want to maximize the sum of the chosen edges. Can be solved with Minimum cost maximum flow. Nils Grimsmo 16:22, 6 December 2005 (UTC)
The former is a subset of the latter, wherein all edges have equal weights.
we should mention the difference between maximal matchings and maximum matchings. The first is set-theoretical maximum, which holds that there are no other edge, we can add to the matching without destroying its matching character. The latter is a matching with the maximal number of chosen edges, which is - of course - also maximal. Please corerct my mistakes if ayou see any of them w.r.t. the difference mentiones above.
I think it needs correction: a matching cannot contain an augmenting path (can it? but the graph can). But I'm not familiar with this result so I'm not going to edit it.
- A matching can contain an Augmenting path. A Perfect Matching cannot, and a Maximum Sized Matching (one with the largest number of edges possible) cannot. A single edge in any graph is technically considered a matching. ANY collection of disjoint edges is a matching. Rob 00:52, 25 August 2006 (UTC)
