h1. Algoritmul lui Kuhn(Ungar)

h1. Algoritmul lui Kuhn(Ungar)
 
h2. Introducere
 
Voi prezenta in continuare problema afectarii impreuna cu una din cele mai eficiente solutii pentru rezolvarea ei: _Algoritmul lui Kuhn_. In ultima parte a articolului, voi oferi un exemplu de implementare usor de folosit in concursurile de informatica. Se presupun cunoscute notiunile de *cuplaj maxim* si *suport minim* intr-un graf bipartit, precum si modul de obtinere a unui cuplaj maxim intr-un graf bipartit cu ajutorul drumurilor de crestere. Sa incepem cu definitia problemei discutate.
 
*Problema de afectare*: Exista _m_ muncitori si _n_ lucrari, fiecare muncitor putand efectua una sau mai multe lucrari. Notam muncitorii cu _x ~1~_ , _x ~2~_ , ..., _x ~m~_ , lucrarile cu _y ~1~_ , $y ~2~$ , ..., _y ~n~_ , si asociem costul _v ~ij~_  ≤ $0$ efectuarii de catre muncitorul _x ~i~_  a lucrarii _y ~j~_ , faptul ca _v ~ij~_  = ∞ avand semnificatia ca muncitorul _x ~i~_  nu poate efectua lucrarea _y ~j~_ . Sa se gaseasca o repartizare a celor _m_ muncitori la cele _n_ lucrari astfel incat un muncitor sa efectueze cel mult o lucrare, iar o lucrare sa fie efectuata de cel mult un muncitor, cu conditia ca costul total de executie sa fie minim.