NOŢIUNI INTRODUCTIVE. DEFINIŢII
METODE DE REPREZENTARE
Există mai multe moduri de reprezentare a grafurilor, alegerea făcându-se în funcţie de tipurile de operaţii care urmează să se efectueze:
1. Matricea de adiacenţă: face o asociere între noduri şi indicii matricei. Este o matrice simentrică faţă de diagonala principală, cu nXn elemente, unde n este numărul de noduri.
aij= 1, dacă muchia [i,j] există
0, dacă muchia [i,j] nu există
Obs. Numarul de valori “1” de pe linia “i” (sau de pe coloana “i”) reprezintă gradul nodului “i”.
2. Matricea lanţurilor: este o matrice pătratică simetrică faţă de diagonala principală cu nXn elemente, unde n este numărul de noduri.
aij= 1, dacă lanţul de la i la j există
0, dacă lanţul de la i la j nu există
Obs. matricea lanţurilor se obţine din matricea de adiacenţă prin aplicarea algoritmului lui Roy-Warshall. Se utilizează pentru a arăta dacă un graf este conex sau nu. Dacă are în matrice numai valori de 1, insemnă că graful este conex.
3. Matricea costurilor: pentru reprezentarea grafurilor valorice. Este o matrice simentrică faţă de diagonala principală, cu nXn elemente, unde n este numărul de noduri.
aij= costul muchiei, dacă muchia [i,j] există
0, dacă muchia [i,j] nu există
∞, dacă este o problemă de minim (-∞, dacă este o problemă de maxim)
4. Lista de adiacenţă reprezentată folosind alocarea dinamică se reţine pentru fiecare nod lista vecinilor
a) se foloseşte un vector care reţine adresa de început a listei vecinilor fiecărui nod
b) se foloseşte o listă care reţine adresa de început a listei vecinilor fiecărui nod
5. Lista de adiacenţă reprezentată folosind tablouri bidimensionale cu n+2m coloane şi două linii (n=numărul de noduri, m=numărul de muchii), pe prima linie se scriu numerele de la 1 la n+2m, iar pe a doua se reţine în coloanele de la 1 la n coloana în care apare primul vecin al său, iar pe coloanele de la n+1 la n+2m coloana pe care se află următorul vecin al nodului.
6. Doi vectori: se reţine un capăt al muchiei într-un vector, iar celălalt capăt în al doilea vector. Lungimea vecorilor este egală cu numărul de muchii.
7. Un vector de muchii: se defineşte tipul muchie (reţine capetele muchiei si eventual costul-pentru grafuri valorizate), apoi definim un vector de muchii care are atâtea componente câte muchii sunt
8. lista de muchii: se defineşte tipul nod care reţine capetele muchiei şi eventual costul - pentru grafuri valorice.
Probleme propuse:
Fie G un graf neorientat, cu n vârfuri si m muchii, reprezentat prin matricea de adiacentă.
Să se realizeze programe, în C/C++, care:
a) afisează gradele tuturor vârfurilor;
b) afisează vârfurile de grad par;
c) afisează vârfurile izolate;
d) afisează vârfurile terminale;
e) verifică dacă graful are vârfuri izolate;
t) verifică dacă graful are vârfuri terminale;
g) verifică dacă graful are vârfuri interioare (nu sunt nici izolate nici terminale);
h) verifică dacă graful are toate vârfurile izolate;
i) verifică dacă graful are toate vârfurile interioare (nu sunt nici izolate nici terminale);
j) afisează gradul unui vârf dat;
k) afisează vecinii unui nod dat, vf;
l) verifică dacă un vârf dat este terminal, izolat sau interior;
m) afisează gradul cel mai mare si toate vârfurile care au acest grad
n) afisează frecventa vârfurilor:
izolate : n1
terminale : n2
interioare : n3
Aplicaţii cu grafuri neorientate
1. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru:
a) Citirea grafului;
b) Afişaţi matricea de adiacenţă a grafului;
c) Afişaţi gradele tuturor nodurilor
d) Afişaţi toate nodurile de grad maxim
e) Afişaţi toate nodurile terminale
f) Afişaţi toate nodurile izolate
2. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru:
a) Citirea grafului;
b) Afişaţi listele de adiacenta;
c) Afisati varfurile cu numar maxim de vecini;
d) Afisati varfurile cu un singur vecin;
e) Afisati varfurile fara vecini
3. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru:
a) Citirea grafului;
b) Afişaţi matricea de adiacenţă a grafului;
c) Afişaţi parcurgerile in latime din fiecare varf
4. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru:
a) Citirea grafului;
b) Afişaţi matricea de adiacenţă a grafului;
c)Afişaţi parcurgerile in adancime din fiecare varf
5. Din fişierul graf.in se citeşte de pe prima linie valorile n (numărul de noduri) şi m (numărul de muchii) ale unui graf neorientat G=(X,U). De pe următoarele m linii se citeşte lista muchiilor. Scrieţi funcţiile pentru:
a) Citirea grafului;
b) Afişaţi matricea de adiacenţă a grafului;
c) Afişaţi matricea lanţurilor
</div>