Cardinality-maximal matching: Difference between revisions
| (7 intermediate revisions by the same user not shown) | |||
| Line 12: | Line 12: | ||
A matching <math>M</math> in <math>G</math> such that <math>|M'|\leq|M|</math> for any other matching <math>M'</math> in <math>G</math>. | A matching <math>M</math> in <math>G</math> such that <math>|M'|\leq|M|</math> for any other matching <math>M'</math> in <math>G</math>. | ||
== Known algorithms: == | |||
# [[Classical bipartite cardinality matching]] ([[Basic graph definitions#Bipartite and k-partite graphs|bipartite]] graphs <math>G</math> only) | |||
# [[Maximum matching by Edmonds]] | # [[Maximum matching by Edmonds]] | ||
== Berge's theorem == | == Berge's theorem == | ||
'''Statement:''' | '''Statement:''' | ||
A matching <math>M</Math> in an undirected graph <math>G=(V,E)</math> is cardinality-maximal if, and only if, <math>M</math> admits no [[Matchings in graphs# | A matching <math>M</Math> in an undirected graph <math>G=(V,E)</math> is cardinality-maximal if, and only if, <math>M</math> admits no [[Matchings in graphs#Alternating and augmenting paths|augmenting path]]. | ||
'''Proof:''' | '''Proof:''' | ||
Clearly, if <math>M</math> admits an augmenting path, <math>M</math> is not cardinality-maximal. So consider the case that <math>M</math> is not cardinality-maximal. We have to show that <math>M</math> admits an augmenting path. | Clearly, if <math>M</math> admits an augmenting path, <math>M</math> is not cardinality-maximal. So consider the case that <math>M</math> is not cardinality-maximal. We have to show that <math>M</math> admits an augmenting path. | ||
By assumption, there is a matching <math>M'</math> in <math>G</math> such that <math>|M'|>|M|</math>. Let <math>\Delta:=(M\setminus M'\cup(M'\setminus M)</math> denote the symmetric difference of <math>M</math> and <math>M'</math>. Obviously, any node <math>v\in V</math> is incident to at most two edges in <math>\Delta</math>. Consequently, <math>\Delta</math> decomposes into [[Basic graph definitions#Paths|node-disjoint paths]] (some of them may be [[Basic graph definitions#Cycles|cycles]]). These paths are [[Matchings in graphs# | By assumption, there is a matching <math>M'</math> in <math>G</math> such that <math>|M'|>|M|</math>. Let <math>\Delta:=(M\setminus M')\cup(M'\setminus M)</math> denote the symmetric difference of <math>M</math> and <math>M'</math>. Obviously, any node <math>v\in V</math> is incident to at most two edges in <math>\Delta</math>. Consequently, <math>\Delta</math> decomposes into [[Basic graph definitions#Paths|node-disjoint paths]] (some of them may be [[Basic graph definitions#Cycles|cycles]]). These paths are [[Matchings in graphs#Alternating and augmenting paths|alternating]]. Since <math>|M'|>|M|</math>, at least one of these paths must be [[Matchings in graphs#Alternating and augmenting paths|augmenting]]. | ||
'''Remark:''' | |||
As a by-product, the following result is proved as well: Let <math>k</math> be the difference between <math>|M|</math> and the maximal cardinality of a matching. Then there are at least <math>k</math> node-disjoint augmenting paths. | |||
Latest revision as of 09:51, 6 December 2014
Basic definitions
Definition
Input: An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\leq|M| }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].
Known algorithms:
- Classical bipartite cardinality matching (bipartite graphs [math]\displaystyle{ G }[/math] only)
- Maximum matching by Edmonds
Berge's theorem
Statement: A matching [math]\displaystyle{ M }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is cardinality-maximal if, and only if, [math]\displaystyle{ M }[/math] admits no augmenting path.
Proof: Clearly, if [math]\displaystyle{ M }[/math] admits an augmenting path, [math]\displaystyle{ M }[/math] is not cardinality-maximal. So consider the case that [math]\displaystyle{ M }[/math] is not cardinality-maximal. We have to show that [math]\displaystyle{ M }[/math] admits an augmenting path.
By assumption, there is a matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ |M'|\gt |M| }[/math]. Let [math]\displaystyle{ \Delta:=(M\setminus M')\cup(M'\setminus M) }[/math] denote the symmetric difference of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ M' }[/math]. Obviously, any node [math]\displaystyle{ v\in V }[/math] is incident to at most two edges in [math]\displaystyle{ \Delta }[/math]. Consequently, [math]\displaystyle{ \Delta }[/math] decomposes into node-disjoint paths (some of them may be cycles). These paths are alternating. Since [math]\displaystyle{ |M'|\gt |M| }[/math], at least one of these paths must be augmenting.
Remark: As a by-product, the following result is proved as well: Let [math]\displaystyle{ k }[/math] be the difference between [math]\displaystyle{ |M| }[/math] and the maximal cardinality of a matching. Then there are at least [math]\displaystyle{ k }[/math] node-disjoint augmenting paths.