CURSUL nr.10

GRAFURI

1. Probleme practice care necesita utilizarea acestei structuri de cdate:
   - executia reparatiilor capitale
   - realizarea proceselor de asamblare a produselor complexe
   - realizarea de constructii.
   Se descriu:
   - liste de activitati, cu durate
   - liste de materiale, echipamente, executanti pe calificari
   - precedente ale activitatilor.
   Este important sa se realizeze un management al datelor pentru ca absenta unei activitati
   sau a unui echipament sau a uneor specialisti deregleaza intregul proces, conducand la o solutie
   mai slaba decat oricare alta obtinuta fara proces de optimizare.
   
2. Reprezentarea grafului cu ajutorul matricelor preesupune:
   - construirea unei matrice patrate cu atatea linii si coloane cate noduri are graful
   - la intersectia liniei i si coloanei j se trece 1 daca exista arc de la nodul
   N_i pleaca arc spre nodul N_j, iar zero in caz contrar.
   Sunt multe noduri care nu au arce si de aceea este mai bine sa se reprezinte graful ca matrice rara.
   
3. Reprezentarea prin vector si liste simple presupune sa se construiasca
   un vector de structura cu atatea elemente cate noduri are graful.
   Un element contine:
   - nume nod
   - un pointer spre elementele unei liste simple.
   Lista simpla contine elemente ce au in structura campuri referitoare la:
   - nodul destinatie
   - caracteristici ale activitatilor si resurselor utilizate.
   
4. Reprezentarea prin agregari de liste care vizeaza:
   - o lista de baza cu continut la fel cu elementele vectorului de structura
   - liste derivate care au atatea elelente cate arce incidente spre exterior are nodul
   ce corespunde elementului din lista de baza.
5. Functiile care opereaza pe structura graf vizeaza:
   - alocare zone de memorie si initializare
   - creare de structura fie ca vector cu liste fie ca liste de liste
   - traversarea grafului
   - inserare de noduri
   - inserare de arce
   - stergere noduri
   - stergere arce
   - calcul de drumuri de lungime minima, respectiv, maxima.
   Trebuie sa existe multe chei de verificare a completitudinii si corectitudinii datelor cu care se descriu grafurile.
   

in lucru acum....

REVENIRE