|
|
Ci sono due tipi di realizzazioni:
matrice incidenza nodi-archi
matrice adiacenza nodi-nodi
La matrice di incidenza nodi-archi è una matrice rettangolare B di dimensione n x m, dove ciascuna riga rappresenta un nodo e ciascuna colonna un arco, tale che:
La rappresentazione grafica sarà la seguente:
La determinazione dell' insieme di adiacenza è piuttosto complicata.
Per calcolare l’insieme di adiacenza A(u) del nodo u, occorre infatti scandire la riga u di B
per trovare posizioni con il –1, poi per ciascuna di queste posizioni occorre poi
scandire la colonna per trovare dei +1, con complessità O(n m).
La matrice di adiacenza nodi-nodi è una matrice quadrata E di dimensione n x n, tale che:
dove A e l’ insieme delle adiacenze. La rappresentazione grafica sarà la seguente:
Determinazione un insieme di adiacenza risulta molto semplice, per calcolare A(u) basta scandire la riga corrispondente. Per la scansione di tutti gli archi la complessità è O(n2).
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.