Matchings in graphs: Difference between revisions
Jump to navigation
Jump to search
m (→Blossoms: insgesamt häufiger u_B verwendet, daher nun in diese Richtung abgeändert) |
|||
| (7 intermediate revisions by 2 users not shown) | |||
| Line 2: | Line 2: | ||
# Let <math>G=(V,E)</math> be an [[Basic graph definitions|undirected graph]]. Without loss of generality, <math>G</math> is [[Basic graph definitions#Connectedness|connected]]. 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]]. Without loss of generality, <math>G</math> is [[Basic graph definitions#Connectedness|connected]]. 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]]. | ||
# An edge in <math>M</math> is called '''matched''', | # An edge in <math>M</math> is called '''matched''', an edge in <math>E\setminus M</math> is '''unmatched'''. | ||
# A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a | # A node <math>v\in V</math> is '''matched''' with respect to a matching <math>M</math> if it is incident to a matched edge; otherwise, <math>v</math> is called '''free''' or '''exposed'''. | ||
# A matching is called '''perfect''' if there is no exposed node. | # A matching is called '''perfect''' if there is no exposed node. | ||
| Line 11: | Line 11: | ||
== Alternating and augmenting paths == | == 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 | # 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 successive 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>. | ||
# | # An alternating 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 both of its end nodes are exposed. | ||
# '''Augmenting''' a matching <math>M</math> along an augmenting path <math>p</math> means increasing the size of <math>M</math> by one as follows: | # '''Augmenting''' a matching <math>M</math> '''along an augmenting path''' <math>p</math> means increasing the size of <math>M</math> by one as follows: | ||
## 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>. | ||
| Line 25: | Line 25: | ||
'''Remark on the implementation:''' | '''Remark on the implementation:''' | ||
This modified graph traversal in an undirected graph could be implemented as | This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph: | ||
# Duplicate each matched node <math>v</math> giving <math>v_1</math> and <math>v_2</math>. | # Duplicate each matched node <math>v</math> giving <math>v_1</math> and <math>v_2</math>. | ||
# Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>. | # Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>. | ||
| Line 31: | Line 31: | ||
## Let all incoming arcs of <math>v</math> in <math>M</math> point to <math>v_1</math> and all outgoing arcs in <math>E\setminus M</math> leave <math>v_1</math>. | ## Let all incoming arcs of <math>v</math> in <math>M</math> point to <math>v_1</math> and all outgoing arcs in <math>E\setminus M</math> leave <math>v_1</math>. | ||
## Mirror-symmetrically, let all incoming arcs of <math>v</math> in <math>E\setminus M</math> point to <math>v_2</math> and all outgoing arcs of <math>v</math> in <math>M</math> leave <math>v_2</math>. | ## Mirror-symmetrically, let all incoming arcs of <math>v</math> in <math>E\setminus M</math> point to <math>v_2</math> and all outgoing arcs of <math>v</math> in <math>M</math> leave <math>v_2</math>. | ||
'''Caveat:''' | |||
If the graph is not [[Basic graph definitions#Bipartite and k-partite graphs|bipartite]], no [[Graph traversal|graph traversal strategies]], modified as described above, guarantees to find an augmenting path if there is one; [[#Blossoms|blossom handling]] is necessary in addition. | |||
== Blossoms == | == Blossoms == | ||
'''Definitions:''' | '''Definitions:''' | ||
# | # For a matching <math>M</math> in <math>G</math>, a '''blossom''' is a cycle <math>B</math> of odd length in <math>G</math> such that <math>\lfloor|B|/2\rfloor</math> edges on <math>B</math> are matched and the remaining node on <math>B</math> is matched as well (by an edge not on <math>B</math>, in fact). | ||
# The unique matched edge with exactly one incident node on < | # The unique matched edge with exactly one incident node on <math>B</math> is called the '''stem''' of the blossom. | ||
# '''Shrinking''' a blossom <math>B</math> means: | # '''Shrinking''' a blossom <math>B</math> means: | ||
## Insert a new node <math>u_B</math> in <math>V</math>. | ## Insert a new node <math>u_B</math> in <math>V</math>. | ||
## For each edge <math>\{v,w\}</math> such that <math>v</math> is on <math>B</math> and <math>w</math> is not: Replace <math>\{v,w\}</math> by a new edge <math>\{ | ## For each edge <math>\{v,w\}</math> such that <math>v</math> is on <math>B</math> and <math>w</math> is not: Replace <math>\{v,w\}</math> by a new edge <math>\{u_B,w\}</math>. | ||
## Remove all nodes and edges on <math>B</math>. | ## Remove all nodes and edges on <math>B</math>. | ||
# An augmenting path <math>p</math> '''conforms''' to <math>B</math> if <math>p</math> contains the stem. | # An augmenting path <math>p</math> '''conforms''' to <math>B</math> if <math>p</math> contains the stem. | ||
'''Statement:''' | '''Statement:''' | ||
Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>B</math> a blossom. Further, let <math>G'=(V',E')</math> be the undirected graph resulting from shrinking <math>B</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is | Let <math>G=(V,E)</math> be an undirected graph, <math>M</math> a matching in <math>G</math>, and <math>B</math> a blossom. Further, let <math>G'=(V',E')</math> be the undirected graph resulting from shrinking <math>B</math>, and let <math>M'</math> be the restriction of <math>M</math> to <math>G'</math>. There is an augmenting path conforming to <math>B</math> in <math>G</math> with respect to <math>M</math> if, and only if, there is an augmenting path in <math>G'</math> with respect to <math>M'</math> that contains <math>u_B</math>. | ||
'''Proof:''' | '''Proof:''' | ||
First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>B</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>u_B</math>. | First suppose there is a conforming augmenting path <math>p</math> in <math>G</math> with respect to <math>M</math>. According to either possible orientation of <math>p</math>, let <math>s</math> and <math>t</math> denote the first and the last node of <math>p</math>. Moreover, let <math>v</math> and <math>w</math> denote the first and the last node of <math>p</math> that also belongs to <math>B</math> (possibly <math>v=w</math>). The concatenation of the subpaths of <math>p</math> from <math>s</math> to <math>v</math> and from <math>w</math> to <math>t</math> is an augmenting path in <math>G'</math>, and this path contains <math>u_B</math>. | ||
So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>u_B</math>. | So, consider the case that there is an augmenting path <math>p</math> in <math>G'</math> with respect to <math>M'</math>, and that <math>p</math> contains <math>u_B</math>. Since <math>u_B</math> is matched, <math>u_B</math> is not an end node of <math>p</math>, so <math>p</math> contains the stem of <math>B</math> because this is the only matched edge incident to <math>u_B</math>. Let <math>v</math> be the node of <math>B</math> incident to the stem and let <math>w</math> be the node on <math>p</math> that is farthest away from <math>v</math> on <math>p</math> among all nodes of <math>p</math> that also belong to <math>B</math>. Exactly one of the two subpaths of <math>B</math> from <math>v</math> to <math>w</math> yields a conforming augmenting path by concatenation with the two subpaths of <math>p</math> from the end nodes of <math>p</math> up to <math>v</math> and <math>w</math>, respectively. | ||
Latest revision as of 09:53, 22 February 2015
Matchings
- Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph. Without loss of generality, [math]\displaystyle{ G }[/math] is connected. 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.
- An edge in [math]\displaystyle{ M }[/math] is called matched, an edge in [math]\displaystyle{ E\setminus M }[/math] is unmatched.
- 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 matched edge; otherwise, [math]\displaystyle{ v }[/math] is called free or exposed.
- A matching is called perfect if there is no exposed node.
Remark: 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 successive 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].
- An alternating 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 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].
Finding augmenting paths
To find alternating paths in a matching [math]\displaystyle{ M }[/math], a graph traversal strategy is chosen and modified as follows:
- Whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ M }[/math], only incident edges in [math]\displaystyle{ E\setminus M }[/math] are considered for seeing new nodes.
- Mirror-symmetrically, whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ E\setminus M }[/math], only the (unique) incident edge in [math]\displaystyle{ M }[/math], if existing, is considered for seeing a new node.
To find augmenting paths, the start node must be an exposed node.
Remark on the implementation: This modified graph traversal in an undirected graph could be implemented as an ordinary graph traversal in a directed graph:
- Duplicate each matched node [math]\displaystyle{ v }[/math] giving [math]\displaystyle{ v_1 }[/math] and [math]\displaystyle{ v_2 }[/math].
- Replace each edge [math]\displaystyle{ \{v,w\} }[/math] by two arcs, [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math].
- For each matched node [math]\displaystyle{ v }[/math]:
- Let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] point to [math]\displaystyle{ v_1 }[/math] and all outgoing arcs in [math]\displaystyle{ E\setminus M }[/math] leave [math]\displaystyle{ v_1 }[/math].
- Mirror-symmetrically, let all incoming arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ E\setminus M }[/math] point to [math]\displaystyle{ v_2 }[/math] and all outgoing arcs of [math]\displaystyle{ v }[/math] in [math]\displaystyle{ M }[/math] leave [math]\displaystyle{ v_2 }[/math].
Caveat: If the graph is not bipartite, no graph traversal strategies, modified as described above, guarantees to find an augmenting path if there is one; blossom handling is necessary in addition.
Blossoms
Definitions:
- For a matching [math]\displaystyle{ M }[/math] in [math]\displaystyle{ G }[/math], a blossom is a cycle [math]\displaystyle{ B }[/math] of odd length in [math]\displaystyle{ G }[/math] such that [math]\displaystyle{ \lfloor|B|/2\rfloor }[/math] edges on [math]\displaystyle{ B }[/math] are matched and the remaining node on [math]\displaystyle{ B }[/math] is matched as well (by an edge not on [math]\displaystyle{ B }[/math], in fact).
- The unique matched edge with exactly one incident node on [math]\displaystyle{ B }[/math] is called the stem of the blossom.
- Shrinking a blossom [math]\displaystyle{ B }[/math] means:
- Insert a new node [math]\displaystyle{ u_B }[/math] in [math]\displaystyle{ V }[/math].
- For each edge [math]\displaystyle{ \{v,w\} }[/math] such that [math]\displaystyle{ v }[/math] is on [math]\displaystyle{ B }[/math] and [math]\displaystyle{ w }[/math] is not: Replace [math]\displaystyle{ \{v,w\} }[/math] by a new edge [math]\displaystyle{ \{u_B,w\} }[/math].
- Remove all nodes and edges on [math]\displaystyle{ B }[/math].
- An augmenting path [math]\displaystyle{ p }[/math] conforms to [math]\displaystyle{ B }[/math] if [math]\displaystyle{ p }[/math] contains the stem.
Statement: Let [math]\displaystyle{ G=(V,E) }[/math] be an undirected graph, [math]\displaystyle{ M }[/math] a matching in [math]\displaystyle{ G }[/math], and [math]\displaystyle{ B }[/math] a blossom. Further, let [math]\displaystyle{ G'=(V',E') }[/math] be the undirected graph resulting from shrinking [math]\displaystyle{ B }[/math], and let [math]\displaystyle{ M' }[/math] be the restriction of [math]\displaystyle{ M }[/math] to [math]\displaystyle{ G' }[/math]. There is an augmenting path conforming to [math]\displaystyle{ B }[/math] in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ M }[/math] if, and only if, there is an augmenting path in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M' }[/math] that contains [math]\displaystyle{ u_B }[/math].
Proof: First suppose there is a conforming augmenting path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G }[/math] with respect to [math]\displaystyle{ M }[/math]. According to either possible orientation of [math]\displaystyle{ p }[/math], let [math]\displaystyle{ s }[/math] and [math]\displaystyle{ t }[/math] denote the first and the last node of [math]\displaystyle{ p }[/math]. Moreover, let [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math] denote the first and the last node of [math]\displaystyle{ p }[/math] that also belongs to [math]\displaystyle{ B }[/math] (possibly [math]\displaystyle{ v=w }[/math]). The concatenation of the subpaths of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ s }[/math] to [math]\displaystyle{ v }[/math] and from [math]\displaystyle{ w }[/math] to [math]\displaystyle{ t }[/math] is an augmenting path in [math]\displaystyle{ G' }[/math], and this path contains [math]\displaystyle{ u_B }[/math].
So, consider the case that there is an augmenting path [math]\displaystyle{ p }[/math] in [math]\displaystyle{ G' }[/math] with respect to [math]\displaystyle{ M' }[/math], and that [math]\displaystyle{ p }[/math] contains [math]\displaystyle{ u_B }[/math]. Since [math]\displaystyle{ u_B }[/math] is matched, [math]\displaystyle{ u_B }[/math] is not an end node of [math]\displaystyle{ p }[/math], so [math]\displaystyle{ p }[/math] contains the stem of [math]\displaystyle{ B }[/math] because this is the only matched edge incident to [math]\displaystyle{ u_B }[/math]. Let [math]\displaystyle{ v }[/math] be the node of [math]\displaystyle{ B }[/math] incident to the stem and let [math]\displaystyle{ w }[/math] be the node on [math]\displaystyle{ p }[/math] that is farthest away from [math]\displaystyle{ v }[/math] on [math]\displaystyle{ p }[/math] among all nodes of [math]\displaystyle{ p }[/math] that also belong to [math]\displaystyle{ B }[/math]. Exactly one of the two subpaths of [math]\displaystyle{ B }[/math] from [math]\displaystyle{ v }[/math] to [math]\displaystyle{ w }[/math] yields a conforming augmenting path by concatenation with the two subpaths of [math]\displaystyle{ p }[/math] from the end nodes of [math]\displaystyle{ p }[/math] up to [math]\displaystyle{ v }[/math] and [math]\displaystyle{ w }[/math], respectively.