Rappresentazione Matematica di grafi Flashcards
RM di un grafo non pesato
Si fa con la matrice di adiacenza di un grafo:
- Matrice quadrata nxn chiamata A(G).
- A(i,j) = 1 se vj appartiene a Γvi e 0 altrimenti.
Simmetria di A(G)
Se g non è orientato allora sappiamo che se vi appartiene a Γvj allora anche vj appartiene a Γvi.
Perciò avremo che A(i,j) = A(j,i) e quindi la matrice di adiacenza è simmetrica A= At.
Se g è orientato allora non è detto che A(i,j)=A(j,i) quindi non possiamo dire con certezza che A(G) sia simmetrica.
Vicinato e predecessori in A(G)
Il vicinato N(vi) è dato dagli elementi della i riga diversi da 0.
I predecessori di vj sono dati dagli elementi della colonna j diversi da 0.
Somma elementi della i riga e della j colonna
Se g non orientato allora la somma degli elementi della i riga mi da il grado di vi.
Che è uguale alla somma degli elementi della j colonna.
Se g è orientato allora:
- la somma degli elementi della i riga mi da il grado uscente di vi.
- la somma degli elementi della j colonna mi da il grado entrante di vj.
RM di un multigrafo
A(G):
- matrice quadrata nxn
- A(i,j)= nij se esistono n archi incidenti in vi e vj, 0 altrimenti.
