Hungarian method: Difference between revisions
Jump to navigation
Jump to search
(Created page with "== Abstract view == '''Algorithmic problem:''' Maximum-weight matching in [Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] <math>G=(V_1\dot\cup...") |
|||
| Line 6: | Line 6: | ||
'''Auxiliary data:''' | '''Auxiliary data:''' | ||
# A real number <math> | # A real number <math>x(v)</math> for each node <math>v\in V_1</math>. | ||
# A real number <math> | # A real number <math>y(w)</math> for each node <math>w\in V_2</math>. | ||
'''Invariant:''' | '''Invariant:''' | ||
# For each edge <math>e=\{v,w\}\in E</math>, where <math>v\in V_1</math> and <math>w\in V_2</math>, it is <math>c(e)\leq x(v)+y(w)</math>. | # For each edge <math>e=\{v,w\}\in E</math>, where <math>v\in V_1</math> and <math>w\in V_2</math>, it is <math>c(e)\leq x(v)+y(w)</math>. | ||
'''Variant:''' | |||
'''Break condition:''' | |||
For each edge <math>e=\{v,w\} in E</math>, where <math>v\in V_1</math> and <math>w\in V_2</math>, it is <math>c(e)=x(v)+y(w)</math>. | |||
== Induction basis == | |||
Initialize all <math>x</math> and <math>y</math> values such that the invariant is fulfilled, for example: | |||
# <math>x(v):=\max\{c(\{v,w\}}|w\in V_2\}</math> for all <math>v\in V</math>. | |||
# <math>y(w):=0</math> for all <math>w\in V:2</math>, | |||
== Induction step == | |||
Revision as of 18:51, 22 November 2014
Abstract view
Algorithmic problem: Maximum-weight matching in [Basic graph definitions#Bipartite and k-partite graphs|bipartite graphs]] [math]\displaystyle{ G=(V_1\dot\cup V_2,E) }[/math].
Type of algorithm: loop.
Auxiliary data:
- A real number [math]\displaystyle{ x(v) }[/math] for each node [math]\displaystyle{ v\in V_1 }[/math].
- A real number [math]\displaystyle{ y(w) }[/math] for each node [math]\displaystyle{ w\in V_2 }[/math].
Invariant:
- For each edge [math]\displaystyle{ e=\{v,w\}\in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)\leq x(v)+y(w) }[/math].
Variant:
Break condition: For each edge [math]\displaystyle{ e=\{v,w\} in E }[/math], where [math]\displaystyle{ v\in V_1 }[/math] and [math]\displaystyle{ w\in V_2 }[/math], it is [math]\displaystyle{ c(e)=x(v)+y(w) }[/math].
Induction basis
Initialize all [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] values such that the invariant is fulfilled, for example:
- [math]\displaystyle{ x(v):=\max\{c(\{v,w\}}|w\in V_2\} }[/math] for all [math]\displaystyle{ v\in V }[/math].
- [math]\displaystyle{ y(w):=0 }[/math] for all [math]\displaystyle{ w\in V:2 }[/math],