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, complet, cu costuri, să se determine un ciclu hamiltonian de cost cât mai mic, utilizând metoda euristică care pleacă de la o mulţime vidă de muchii, consideră muchiile grafului în ordine crescătoare a costurilor şi adaugă o muchie la mulţime dacă şi numai dacă nu rezultă un ciclu care nu e hamiltonian.
2. Dându-se un graf orientat şi două vârfuri, să se determine un drum elementar de lungime maximă între ele.
3. Dându-se un graf orientat, să se determine un ciclu hamiltonian (dacă există).
4. Dându-se un graf neorientat, complet, cu costuri, să se determine un ciclu hamiltonian de cost cât mai mic, utilizând metoda euristică care pleacă de la un drum de lungime zero şi adaugă la el, în mod repetat, muchia cu costul cel mai mic dintre cele incidente unuia dintre capete.
5. Dându-se un graf neorientat, să se determine un ciclu hamiltonian (dacă există).
6. Dându-se un graf orientat, cu costuri, şi două vârfuri, să se determine un drum elementar de cost minim între vârfurile date (pot exista circuite de cost negativ).
Probleme suplimentare (bonificaţie)
1B. Dându-se un graf neorientat, complet, cu costuri pozitive ce satisfac inegalitatea triunghiului (c(x,z)<=c(x,y)+c(y,z)), să se determine, in timp polinomial, un ciclu hamiltonian de cost cel mult egal cu dublul costului ciclului hamiltonian de cost minim.
Radu-Lucian LUPŞA