Alternating paths algorithm: Difference between revisions

From Algowiki
Jump to navigation Jump to search
No edit summary
 
(7 intermediate revisions by the same user not shown)
Line 2: Line 2:
[[Category:Maximum matching problem]]
[[Category:Maximum matching problem]]


'''Algorithmic Problem:''' [[Matchings in graphs]].


'''Algorithmic problem:''' The graph <math>G</math> is biparite.
'''Prerequisites:''' The graph <math>G</math> is [[Bipartite graph|bipartite]].
'''Type of algorithm:''' loop
 
'''Auxillary data:'''
'''Type of algorithm:''' loop
 
'''Auxillary data:'''


== Abstract view ==
== Abstract view ==


'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.  
'''Invariant:''' Before and after each iteration, <math>M</math> is a matching.  
'''Variant:''' <math>|M|</math> increases by <math>1</math>.
 
'''Break condition:''' There is no more augmenting alternating path.
'''Variant:''' <math>|M|</math> increases by <math>1</math>.
 
'''Break condition:''' There is no more augmenting alternating path.


== Induction basis ==
== Induction basis ==


'''Abstract view:''' <math>M</math> is initialized to be some matching, for example,  <math>M:=\empty1</math>.
'''Abstract view:''' <math>M</math> is initialized to be some matching, for example,  <math>M:=\empty</math>.
'''Implementation:''' Obvious.
 
'''Proof:''' Nothing to show.
'''Implementation:''' Obvious.
 
'''Proof:''' Nothing to show.


== Induction step ==
== Induction step ==


'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.
'''Abstract view:''' If there is an augmenting alternating path, use it to increase <math>M</math>; otherwise, terminate the algorithm and return <math>M</math>.
'''Implementation:'''
 
'''Implementation:'''
# Call the algorithm Find augmenting alternating path.
# Call the algorithm Find augmenting alternating path.
# If this call fails, terminate the algorithm and return <math>M</math>.
# If this call fails, terminate the algorithm and return <math>M</math>.
# Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call.
# Otherwise, let <math>E'</math> denote the set of all edges on the path delivered by that call.
# Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math<???</math>  
# Let <math>M</math> be the [http://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] of <math>M</math> and <math>???</math>  
Correctness:
Correctness:


Line 32: Line 40:
   
   
'''Statement:'''
'''Statement:'''
'''Proof:'''
'''Proof:'''


==Further information==
==Further information==

Latest revision as of 13:38, 27 January 2015


Algorithmic Problem: Matchings in graphs.

Prerequisites: The graph [math]\displaystyle{ G }[/math] is bipartite.

Type of algorithm: loop

Auxillary data:

Abstract view

Invariant: Before and after each iteration, [math]\displaystyle{ M }[/math] is a matching.

Variant: [math]\displaystyle{ |M| }[/math] increases by [math]\displaystyle{ 1 }[/math].

Break condition: There is no more augmenting alternating path.

Induction basis

Abstract view: [math]\displaystyle{ M }[/math] is initialized to be some matching, for example, [math]\displaystyle{ M:=\empty }[/math].

Implementation: Obvious.

Proof: Nothing to show.

Induction step

Abstract view: If there is an augmenting alternating path, use it to increase [math]\displaystyle{ M }[/math]; otherwise, terminate the algorithm and return [math]\displaystyle{ M }[/math].

Implementation:

  1. Call the algorithm Find augmenting alternating path.
  2. If this call fails, terminate the algorithm and return [math]\displaystyle{ M }[/math].
  3. Otherwise, let [math]\displaystyle{ E' }[/math] denote the set of all edges on the path delivered by that call.
  4. Let [math]\displaystyle{ M }[/math] be the symmetric difference of [math]\displaystyle{ M }[/math] and [math]\displaystyle{ ??? }[/math]

Correctness:

Complexity

Statement:

Proof:

Further information