Classical bipartite cardinality matching: Difference between revisions
| Line 39: | Line 39: | ||
This modified DFS could be realized by a regular DFS: | This modified DFS could be realized by a regular DFS: | ||
# Duplicate each matched node <math>v</math> giviong <math>v_1</math> and <math>v_2</math>. | # Duplicate each matched node <math>v</math> giviong <math>v_1</math> and <math>v_2</math>. | ||
# Replace each edge <math>\{v,w | # Replace each edge <math>\{v,w\}</math> by two arcs, <math>(v,w)</math> and <math>(w,v)</math>. | ||
# For each matched node <math>v</math>: | # For each matched node <math>v</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>. | ## 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>. | ||
Revision as of 15:02, 17 November 2014
Abstract view
Algorithmic problem: Cardinality-maximal matching in bipartite graphs.
Type of algorithm: loop.
Invariant: [math]\displaystyle{ M }[/math] is a matching in [math]\displaystyle{ G }[/math].
Variant: [math]\displaystyle{ |M| }[/math] is increased by one.
Break condition: There is no more augmenting path.
Induction basis
Abstract view: Initialize [math]\displaystyle{ M }[/math] to be a feasible matching, for example, the empty matching.
Induction step:
Abstract view:
- Search for an augmenting path.
- If there is none, the loop terminates.
- Let [math]\displaystyle{ p }[/math] denote the augmenting path found in step 1.
- Augment [math]\displaystyle{ M }[/math] along [math]\displaystyle{ p }[/math].
Implementation of step 1: From every exposed node, a modified ??? is started. This repeated ??? is finished once an augmenting path has been found. The modification of ??? is as follows:
- Whenever the current node [math]\displaystyle{ v }[/math] has been reached via an edge in [math]\displaystyle{ M }[/math], only edges in [math]\displaystyle{ E\setminus M }[/math] are considered for going forward from [math]\displaystyle{ v }[/math].
- 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) edge in [math]\displaystyle{ M }[/math], if existing, is considered for going forward.
Proof: Basically, we have to show that there is no more augmenting path if this modified DFS does not find one. So suppose for a contradiction that a search from an exposed node [math]\displaystyle{ u }[/math] fails although there is an augmenting path starting in [math]\displaystyle{ u }[/math].
Remark: This modified DFS could be realized by a regular DFS:
- Duplicate each matched node [math]\displaystyle{ v }[/math] giviong [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].