Come Costruire la Versione Matriciale di un Grafo

Un grafo è la rappresentazione visuale di un insieme di elementi, detti ‘nodi’, collegati tra loro da rette o curve, chiamate ‘archi’. Spesso un grafo per essere analizzabile da un punto di vista astratto, o anche solo informatico, necessita di essere trasformato in un insieme di matrici che riassume fedelmente le caratteristiche di partenza. Nella guida vediamo come proprio come costruire la versione matriciale di un grafo.

Ti dico subito che dovrai costruire esattamente due matrici per raccogliere tutte le informazioni originariamente contenute nel tuo grafo di partenza. Esse sono la matrice di distanza e la matrice degli archi. Ipotizza adesso di considerare un grafo così strutturato: il nodo 1 è collegato al nodo 2 da un arco che riproduce una distanza di 7 unità, il nodo 2 è collegato al nodo 3 da un arco che riporta una distanza di 4 unità. Infine il nodo 2 è collegato anche al nodo 4 da un arco che definisce una distanza tra i due nodi di 5 unità.

Le matrici che ti appresti ora a popolare sono tutte quadrate e dotate di un lato costituito da tanti elementi quanti sono i nodi in totale. Nel tuo caso, quindi, avrai due matrici quadrate 4 x 4. Per costruire la matrice di distanza devi semplicemente posizionare nell’elemento (i,j) (cioè riga i-ma e colonna j-ma) della matrice la distanza che separa il nodo i dal nodo j. Secondo il grafo descritto a inizio guida puoi quindi valorizzare l’elemento (1,2) di questa matrice con 7, l’elemento (2,3) con 4 e l’elemento (2,4) con 5. Avrai intuito che questo tipo di matrice è simmetrica, quindi l’elemento (i,j) è uguale a quello (j,i).

Dedicati ora alla costruzione della matrice degli archi. Per farlo è sufficiente che valorizzi ogni suo elemento (i,j) con un valore unitario nel caso in cui puoi verificare la presenza di un arco tra il nodo i e il nodo j e con un valore nullo in caso di relativa assenza. Quindi puoi proporre le seguenti valorizzazioni: elemento (1,2) = 1, elemento (2,3) = 1, elemento (2,4) = 1, data la presenza degli archi tra i nodi indicati. Anche questa è una matrice simmetrica. Una volta valorizzati gli elementi simmetrici, tutti i restanti li devi rappresentare con valori nulli. Quindi, ad esempio, è corretto che indichi l’elemento (1,3) = 0 nella tua matrice degli archi, dato che non esiste un arco che colleghi direttamente il nodo 1 al nodo 3.

Lascia un commento