Scadenţă: săpt. 13-14
Rezolvaţi problemele asignate. În plus, puteţi rezolva dintre problemele suplimentare (pentru bonificaţii) de la sfârşitul paginii. Utilizaţi tipul abstract de date de la laboratorul 1; modificaţi-l la nevoie.
1. Dându-se un graf neorientat, să se determine o clică de dimensiune maximă.
2. Dându-se un graf neorientat, să se determine o mulţime intern stabilă de cardinal maxim.
3. Dându-se un graf neorientat, să se determine o mulţime extern stabilă de cardinal minim.
4. Dându-se un graf neorientat, să se determine o colorare a vârfurilor cu număr minim de culori.
Probleme suplimentare (bonificaţie)
1B. Dându-se un graf neorientat, să se determine, în timp polinomial, o mulţime extern stabilă a cărei cardinal să fie cel mult de două ori mai mare decât numărul de stabilitate externă.
Radu-Lucian LUPŞA