Matchings in graphs: Difference between revisions
Jump to navigation
Jump to search
No edit summary |
No edit summary |
||
| Line 1: | Line 1: | ||
== | == Matchings == | ||
# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. A '''matching''' in <math>G</math> is a set <math>M\subseteq E</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]]. | # Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. A '''matching''' in <math>G</math> is a set <math>M\subseteq E</math> of edges such that no two edges in <math>M</math> are [[Basic graph definitions#Adjacency, incidence, and degree|incident]]. | ||
# A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a member of <math>M</math>; otherwise, <math>v</math> is called '''free''' or '''exposed'''. | # A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a member of <math>M</math>; otherwise, <math>v</math> is called '''free''' or '''exposed'''. | ||
# A matching is called '''perfect''' if there is no exposed node. A perfect matching <math>M</math> is only possible if <math>|V|</math> is even. Then <math>M</math> is perfect if, and only if, <math>|M|=|V|/2</math>. | |||
== Alternating and augmenting paths == | |||
# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</math> if, for any two subsequent edges on <math>p</math>, exactly one of them belongs to <math>M</math>. In other words, the edges in <math>M</math> and the edges not in <math>M</math> appear strictly alternatingly on <math>p</math>. | # A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''alternating''' with respect to some matching <math>M</math> if, for any two subsequent edges on <math>p</math>, exactly one of them belongs to <math>M</math>. In other words, the edges in <math>M</math> and the edges not in <math>M</math> appear strictly alternatingly on <math>p</math>. | ||
# A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''augmenting''' with respect to some matching <math>M</math> if <math>p</math> is alternating and both of its end nodes are exposed. | # A path <math>p</math> in an undirected graph <math>G=(V,E)</math> is called '''augmenting''' with respect to some matching <math>M</math> if <math>p</math> is alternating and both of its end nodes are exposed. | ||
| Line 8: | Line 12: | ||
## Each edge of <math>p</math> that was in <math>M</math> immediately before this augmentation step, is removed from <math>M</math>. | ## Each edge of <math>p</math> that was in <math>M</math> immediately before this augmentation step, is removed from <math>M</math>. | ||
## Each edge of <math>p</math> that was ''not'' in <math>M</math> immediately before this augmentation step, is inserted in <math>M</math>. | ## Each edge of <math>p</math> that was ''not'' in <math>M</math> immediately before this augmentation step, is inserted in <math>M</math>. | ||
Revision as of 10:20, 21 November 2014
Matchings
- Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. A matching in [math]\displaystyle{ G }[/math] is a set [math]\displaystyle{ M\subseteq E }[/math] of edges such that no two edges in [math]\displaystyle{ M }[/math] are incident.
- A node [math]\displaystyle{ v\in V }[/math] is matched with respect to a matching [math]\displaystyle{ M }[/math] if it is incident to a member of [math]\displaystyle{ M }[/math]; otherwise, [math]\displaystyle{ v }[/math] is called free or exposed.
- A matching is called perfect if there is no exposed node. A perfect matching [math]\displaystyle{ M }[/math] is only possible if [math]\displaystyle{ |V| }[/math] is even. Then [math]\displaystyle{ M }[/math] is perfect if, and only if, [math]\displaystyle{ |M|=|V|/2 }[/math].
Alternating and augmenting paths
- A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called alternating with respect to some matching [math]\displaystyle{ M }[/math] if, for any two subsequent edges on [math]\displaystyle{ p }[/math], exactly one of them belongs to [math]\displaystyle{ M }[/math]. In other words, the edges in [math]\displaystyle{ M }[/math] and the edges not in [math]\displaystyle{ M }[/math] appear strictly alternatingly on [math]\displaystyle{ p }[/math].
- A path [math]\displaystyle{ p }[/math] in an undirected graph [math]\displaystyle{ G=(V,E) }[/math] is called augmenting with respect to some matching [math]\displaystyle{ M }[/math] if [math]\displaystyle{ p }[/math] is alternating and both of its end nodes are exposed.
- Augmenting a matching [math]\displaystyle{ M }[/math] along an augmenting path [math]\displaystyle{ p }[/math] means increasing the size of [math]\displaystyle{ M }[/math] by one as follows:
- Each edge of [math]\displaystyle{ p }[/math] that was in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is removed from [math]\displaystyle{ M }[/math].
- Each edge of [math]\displaystyle{ p }[/math] that was not in [math]\displaystyle{ M }[/math] immediately before this augmentation step, is inserted in [math]\displaystyle{ M }[/math].