Acoperire la summit

Această intrare pe tema teoriei graficelor este doar o schiță . Contribuiți la îmbunătățirea acestuia în conformitate cu convențiile Wikipedia .

În teoria graficelor , se spune că acoperirea vertexului sau acoperirea prin vârfuri (în engleză vertex cover) sau acoperirea pentru noduri, un subset S de noduri ale unui grafic G = (V, E) astfel încât toate arcele din E au cel puțin o extremă în S. Problema determinării celei mai mici acoperiri de vârf a unui grafic (numită problemă de acoperire a vârfurilor ) este o binecunoscută problemă de optimizare , studiată în teoria complexității ca exemplu de problemă NP-completă .

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică