Définitions et notations

Soit un graphe biparti $X = (A \cup B, E)$, et une fonction $v : A \cup B \rightarrow \mbox{I\hspace{-.15em}N}$. Une couverture est un sous-ensemble $D \subset A \cup B$ tel que $\forall e = (u, v) \in E$, $u \in D$ ou $v \in D$. Le problème se posant est le suivant : trouver une couverture telle que $\sum_{u \in D}v(u)$ soit minimal.