MEMORAREA UNUI GRAF

 1.        Matricea de adiacenta.

Fie un graf G = (X, U), X = {x₁, x₂, …, x_n}. Asociem lui 1 pe x₁, 2 pe x₂, …               

Astfel reprezentarea grafului va fi o matrice patratica de dimensiune n.

A[i][j]   primeste valoarea 1 daca I si j sunt adiacente

                                         0  in caz contrar

Ex.  Pentru graful de mai sus: G = (X, U) unde X = {1, 2, 3, 4, 5, 6}

                                     U = {[1, 2]; [2, 3]; [1, 4],  [4, 5]; [2, 6]}

2.            Lista de adiacenta

Pentru fiecare nod din graf se pastreaza cate o lista care contine nodurile adiacente cu acesta.

Ex: Pentru graful de mai sus

Metoda constă în crearea / memorarea a doi vectori alfa şi beta definiţi astfel:

       alfa[1] = 1

       alfa[i] = 1 + suma gradelor nodurilor 1, 2, 3, ..., i- 1   sau  

                                                              alfa [i] =  alfa [i-1] + grad (i)

               alfa = (1, 3, 6, 7, 9, 10, 11)

        beta reprezintă înşiruirea nodurilor din coloana din dreapta a tabelului alăturat.

                beta = (2, 4, 1, 3, 6, 2, 1, 5, 4, 2)

3.       Matricea costurilor

Fiecarui muchie i se va atribui un numar Real mai mare ca 0, reperezentand costul muchiei respective

c : U -->  R+  

Astfel c este o matrice patratica de dimensiune n definita astfel:

C[i][j]   primeste valoarea v daca i si j sunt adiacente, iar v reprezinta costul muchiei

                                        ;    0  in caz contrar

4.       Matricea de incidenta

Se noteaza muchiile grafului cu m₁, m₂, …, m_m. Metoda consta in alcatuirea unei matrici B cu n linii si m coloane (n- nr. de varfuri si m – nr. de muchii)

B[i][j]  primeste valoarea 1 daca daca nodul I este incident cu muchia m_j.

                                            0 in rest

5. Cu ajutorul a doua siruri

Se vor construi doua siruri X si Y astfel incat muchia m_i are prima extremitate in sirul x_i iar a doua in sirul y_i