== include(page="template/taskheader" task_id="mvc") ==

Fie un graf *$G$* cu $N$ noduri si $N$ muchii, fiecare nod avand un cost asociat. Numim *acoperire* a grafului $G$ o submultime de noduri a sa, $S$, cu proprietatea ca oricum am selecta o muchie din cele $N$, aceasta are cel putin unul din capetele sale in multimea $S$. *Costul* unei acoperiri este dat de suma costurilor nodurilor incluse in acoperire.

Se cere costul minim al unei acoperiri pentru graful $G$.