Eulero fece da “apripista”alla teoria dei grafi, che ha subito notevoli evoluzioni nel tempo. Per meglio comprenderla è opportuno fornirne alcune definizioni e chiarire fin da subito che l’obiettivo di un grafo è quello di rappresentare grafica- mente le colonne e le righe della matrice di incidenza (spiegata e rappresentata in figura 2.10 a pagina 48).
• Un grafo è costituito da un insieme finito di punti detti nodi o vertici e da un insieme di legami esistenti tra le coppie dei nodi, definiti linee archi o spigoli.
Il grafo viene dunque definito secondo la seguente espressione: G(n, a)
Dove:
- G= è il grafo;
CAPITOLO 2. RISCHIO SISTEMICO E NETWORK THEORY 44
- n= è il numero complessivo dei nodi;
- a= è il numero complessivo degli archi.
• Se i legami esistenti tra coppie di nodi sono orientati, cioè se gli archi sono costituiti da una testa (nodo di arrivo) ed una coda (nodo di partenza), si è in presenza di un grafo orientato caratterizzato da una linea (i, j) che parte dal nodo i (definito predecessore di j) e arriva al nodo j (definito successore di i). Graficamente si ottiene questa rappresentazione:
Figura 2.6: Esempio di arco orientato
Mediante l’analisi della figura sopra riportata si riscontra che i grafi orien- tati sono caratterizzati da frecce (colleganti i nodi/vertici), le quali espri- mono la direzione dei legami (archi). L’intensità delle connessioni inoltre viene indicata attribuendo agli archi un valore numerico, in questo modo si ottengono grafi pesati. Al contrario si è in presenza di un grafo non orientato qualora le coppie di punti risultino non ordinate.
• Un nodo è adiacente se risulta connesso ad un altro nodo da un arco. Que- st’ultimo sarà adiacente se avrà in comune con un altro arco un nodo.
• Il vicinato è il complesso di tutti i nodi definiti adiacenti.
• Se ogni coppia di nodi è collegata da un arco, il grafo (orientato o non orientato) viene definito completo.
• Il grado di un nodo è dato dal numero di archi incidenti sul nodo. Un esempio per comprendere il grado del nodo (denominato anche grado di connessione), in un grafo non orientato, è il seguente:
Figura 2.7: Esempio di un grafo non orientato (Fonte: Wikipedia -L’enciclopedia libera)
La tabella 2.2 di seguito riportata si riferisce al grafo rappresentato in Fi- gura 2.7 e per ciascun nodo indica i nodi ad esso adiacenti ed il suo grado (somma dei nodi adiacenti).
Nodi Nodi adiacenti Grado del nodo
1 2; 5 2 2 1; 3; 5 3 3 2; 4 2 4 3; 5; 6 3 5 1; 2; 4 3 6 4 1
CAPITOLO 2. RISCHIO SISTEMICO E NETWORK THEORY 46
• Il grafo è regolare quando tutti i nodi di un grafo hanno lo stesso grado o cardinalità (se quest’ultimo fosse tre si otterrebbe un grafo cubico).
• Il walk (percorso) è dato da una sequenza precisa di vertici ed archi, ogni vertice sta tra la linea precedente e quella successiva.
• Il path (sentiero) è un percorso costituito da vertici ed archi distinti. Il nume- ro degli archi che lo costituiscono definisce la sua lunghezza.
• Il ciclo o percorso chiuso è il cammino in cui il punto da cui si parte ed il punto in cui si arriva coincidono.
• Il cammino elementare si ottiene quando il ciclo non percorre mai due volte lo stesso vertice.
• Un ciclo euleriano si ottiene quando si percorre una sola volta ciascun arco; il grafo costituito da un ciclo euleriano è definito grafo euleriano. Un grafo connesso e non orientato per essere definito euleriano deve avere tutti i nodi di grado pari.
• Quando un punto di separazione (nodo) ed un ponte (arco) vengono eli- minati si ottiene un grafo disconnesso. Un grafo è disconnesso quando è ca- ratterizzato anche solo da un punto isolato, è invece connesso se esiste un percorso tra ciascuna coppia di punti del grafo (non vi sono punti isolati). • I metodi per rappresentare numericamente un grafo sono tre:
1. matrice di connessione; 2. matrice di incidenza; 3. lista di adiacenza.
Figura 2.8: Esempio di grafo orientato
1. la matrice di connessione adopera una matrice quadrata nxn, in cui n rap- presenta il numero dei vertici del grafo. In questa matrice, dato il generico elemento (i, j), il valore 1 indicherà la presenza di un arco (linea) che collega il punto i con il punto j ed il valore 0 invece indicherà l’assenza di collega- mento. Questa matrice viene utilizzata sia con i grafi orientati sia con quelli non orientati. Per quanto riguarda questi ultimi la matrice risulterà simme- trica, in quanto l’elemento (i, j) risulterà uguale all’elemento (j, i);
CAPITOLO 2. RISCHIO SISTEMICO E NETWORK THEORY 48
2. la matrice di incidenza adopera una matrice nxm in cui n rappresenta il nu- mero dei punti (nodi) ed m il numero delle linee (archi) del grafo. Nume- rando gli archi, il generico elemento (i, j) risulterà 1 qualora la linea (arco) j incida sul punto (nodo) e 0 invece nel caso contrario. Questo per quanto riguarda i grafi non orientati. Nel caso invece dei grafi orientati, il generico elemento (i, j) risulterà 1 se la linea j esce dal punto i (“outdegree ”), -1 se la linea j entra nel nodo i (“indegree ”) e 0 se l’arco j non incide sul nodo i;
Figura 2.10: Matrice di incidenza nxm
3. la lista di adiacenza, invece, riassume ed elenca per ciascun vertice del grafico i corrispondenti vertici adiacenti.
Figura 2.11: Lista di adiacenza
Risulta importante considerare anche le seguenti proprietà: l’eccentricità ed il diametro di un grafo.
La prima misura si riferisce alla distanza più lunga tra un nodo specifico ed un altro qualsiasi. Considerando l’eccentricità più lunga si ottiene il diametro del grafo.
Analizzando il seguente grafo:
CAPITOLO 2. RISCHIO SISTEMICO E NETWORK THEORY 50
si ottiene la seguente matrice delle distanze:
Nodi complessivi Nodo 1 Nodo 2 Nodo 3 Nodo 4 Eccentricità
Nodo 1 0 1 1 2 2
Nodo 2 1 0 1 2 2
Nodo 3 1 1 0 1 1
Nodo 4 2 2 1 0 2
Tabella 2.3: Calcolo dell’eccentricità
La matrice delle distanze indica i passi da effettuare per passare da un nodo i al nodo j (distanza geodetica). A livello pratico, come si può riscontrare nella tabella sopra riportata, la distanza dal nodo 1 al nodo 2 è uguale ad uno perché si compie solo un passo per il raggiungimento dei nodi, la distanza tra il nodo 1 e il nodo 4 invece è pari a 2, in quanto per passare dal nodo 1 al nodo 4 si devono effettuare due passi. L’eccentricità del nodo è data dalla distanza più lunga presente tra un nodo e l’altro. Nella tabella l’eccentricità per esempio del nodo 1 è pari a 2 (distanza massima esistente tra il nodo 1 ed un qualsiasi altro nodo costituente il grafo).