Matchings in graphs: Difference between revisions
(Created page with "http://huffmann.algo.informatik.tu-darmstadt.de/wiki/wiki.algo.informatik.tu-darmstadt.de/index.php/Matchings_in_graphs.html") |
No edit summary |
||
| Line 1: | Line 1: | ||
== Definition == | |||
Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. A '''matching''' in <math>G</math> is a set <math>M</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]]. | |||
== Cardinality-maximal matching == | |||
'''Input:''' | |||
An undirected graph <math>G=(V,E)</math>. | |||
'''Output:''' | |||
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>. | |||
== Maximum weighted matching == | |||
'''Input:''' | |||
# An undirected graph <math>G=(V,E)</math>. | |||
# A '''weight''' <math>w(e)</math> for each edge <math>e\in E</math>. | |||
'''Output:''' | |||
A matching <math>M</math> in <math>G</math> such that <math>\sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e)</math> for any other matching <math>M'</math> in <math>G</math>. | |||
Revision as of 18:09, 24 October 2014
Definition
Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A matching in [math]\displaystyle{ G }[/math] is a set [math]\displaystyle{ M }[/math] of edges such that no two edges in [math]\displaystyle{ M }[/math] are incident.
Cardinality-maximal matching
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].
Maximum weighted matching
Input:
- An undirected graph [math]\displaystyle{ G=(V,E) }[/math].
- A weight [math]\displaystyle{ w(e) }[/math] for each edge [math]\displaystyle{ e\in E }[/math].
Output: A matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \sum_{e\in M'}w(e)\leq\sum_{e\in M}w(e) }[/math] for any other matching [math]\displaystyle{ M' }[/math] in [math]\displaystyle{ G }[/math].