Classical bipartite cardinality matching: Difference between revisions

From Algowiki
Jump to navigation Jump to search
Line 34: Line 34:


'''Proof:'''
'''Proof:'''
Basically, we have to show that there is no more augmenting path if this repeated graph search does not find one. So suppose for a contradiction that a search from an exposed node <math>u</math> fails although there is an augmenting path <math>p</math> from <math>u</math> to some other exposed node <math>v</math>. Then <math>v</math> is not seen by this graph search. Let <math>x</math> be the last node on <math>p</math> seen by this graph search, let <math>e</math> denote the edge over which <math>x</math> was seen, and let <math>e'</math> be the next edge on <math>p</math> (as seen in the direction from <math>u</math> to <math>v</math>). Since <math>e</math> was considered by the graph search and <math>e'</math> was not, we may conclude <math>e,e'\not\in M</math>. Let <math>p'</math> be the subpath of <math>p</math> from <math>u</math> to <math>x</math> and <math>p''</math> the path from <math>u</math> to <math>x</math> in the arborescence. As <math>e'\not\in M</math>, the last edge of <math>p'</math> is in <math>M</math>, so <math>p'</math> has even length. Since <math>e\not\in M</math>, <math>p''</math> has odd legngth. In summary, the concatenation <math>p+p'</math> is a (usually non-simple) cycle of odd length. In particular, <math>G</math> is not bipartite.
Basically, we have to show that there is no more augmenting path if this repeated graph search does not find one. So suppose for a contradiction that a search from an exposed node <math>u</math> fails although there is an augmenting path <math>p</math> from <math>u</math> to some other exposed node <math>v</math>. Then <math>v</math> is not seen by this graph search. Let <math>x</math> be the last node on <math>p</math> seen by this graph search, let <math>e</math> denote the edge over which <math>x</math> was seen, and let <math>e'</math> be the next edge on <math>p</math> (as seen in the direction from <math>u</math> to <math>v</math>). Since <math>e</math> was considered by the graph search and <math>e'</math> was not, we may conclude <math>e,e'\not\in M</math>. Let <math>p'</math> be the subpath of <math>p</math> from <math>u</math> to <math>x</math> and <math>p''</math> the path from <math>u</math> to <math>x</math> in the arborescence. As <math>e'\not\in M</math>, the last edge of <math>p'</math> is in <math>M</math>, so <math>p'</math> has even length. Since <math>e\not\in M</math>, <math>p''</math> has odd length. In summary, the concatenation <math>p+p'</math> is a (usually non-simple) cycle of odd length. In particular, <math>G</math> is not bipartite.


'''Remark:'''
'''Remark:'''

Revision as of 10:39, 21 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:

  1. Search for an augmenting path.
  2. If there is none, the loop terminates.
  3. Let [math]\displaystyle{ p }[/math] denote the augmenting path found in step 1.
  4. Augment [math]\displaystyle{ M }[/math] along [math]\displaystyle{ p }[/math].

Implementation of step 1: In a loop over all exposed nodes [math]\displaystyle{ v }[/math], a graph traversal algorithm is started at [math]\displaystyle{ v }[/math]. An algorithm must be chosen that generates an arborescence rooted at the start node [math]\displaystyle{ v }[/math], for example, a DFS or a BFS. This terminates once an augmenting path has been found. To find an augmenting path, the graph search algorithm is modified as follows:

  1. 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.
  2. 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.

Proof: Basically, we have to show that there is no more augmenting path if this repeated graph search 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 [math]\displaystyle{ p }[/math] from [math]\displaystyle{ u }[/math] to some other exposed node [math]\displaystyle{ v }[/math]. Then [math]\displaystyle{ v }[/math] is not seen by this graph search. Let [math]\displaystyle{ x }[/math] be the last node on [math]\displaystyle{ p }[/math] seen by this graph search, let [math]\displaystyle{ e }[/math] denote the edge over which [math]\displaystyle{ x }[/math] was seen, and let [math]\displaystyle{ e' }[/math] be the next edge on [math]\displaystyle{ p }[/math] (as seen in the direction from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ v }[/math]). Since [math]\displaystyle{ e }[/math] was considered by the graph search and [math]\displaystyle{ e' }[/math] was not, we may conclude [math]\displaystyle{ e,e'\not\in M }[/math]. Let [math]\displaystyle{ p' }[/math] be the subpath of [math]\displaystyle{ p }[/math] from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ x }[/math] and [math]\displaystyle{ p'' }[/math] the path from [math]\displaystyle{ u }[/math] to [math]\displaystyle{ x }[/math] in the arborescence. As [math]\displaystyle{ e'\not\in M }[/math], the last edge of [math]\displaystyle{ p' }[/math] is in [math]\displaystyle{ M }[/math], so [math]\displaystyle{ p' }[/math] has even length. Since [math]\displaystyle{ e\not\in M }[/math], [math]\displaystyle{ p'' }[/math] has odd length. In summary, the concatenation [math]\displaystyle{ p+p' }[/math] is a (usually non-simple) cycle of odd length. In particular, [math]\displaystyle{ G }[/math] is not bipartite.

Remark: This modified graph traversal in an undirected graph could be implemented as a regular graph traversal in a directed graph:

  1. Duplicate each matched node [math]\displaystyle{ v }[/math] giving [math]\displaystyle{ v_1 }[/math] and [math]\displaystyle{ v_2 }[/math].
  2. Replace each edge [math]\displaystyle{ \{v,w\} }[/math] by two arcs, [math]\displaystyle{ (v,w) }[/math] and [math]\displaystyle{ (w,v) }[/math].
  3. For each matched node [math]\displaystyle{ v }[/math]:
    1. 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].
    2. 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].