I grafi

Un grafo è una struttura relazionale formata da un numero finito V di vertici ( o nodi ) e un numero finito E di segmenti ( archi o spigoli ) che collegano ogni nodo agli altri.

Un esempio pratico di grafo

Ecco un esempio pratico di grafo

un esempio pratico di grafo

Definizione matematica di grafo

Un grafo è una relazione n-aria su un insieme finito S definita dai sottoinsiemi di S con n elementi che soddisfano una proprietà P(1,...,n).

La definizione matematica è sempre un po' difficile per spiegare un concetto informatico, quindi proverò a descrivere il concetto di grafo anche in modo pratico.

Per indicare un grafo utilizzo la notazione seguente:

G(V,E)

Dove V è l'insieme di tutti i nodi e E è l'insieme di tutti gli archi del grafo.

i nodi e gli archi del grafo

I nodi del grafo

L'insieme dei nodi è indicato con la notazione

V(G)

Esempio

Riprendendo il grafo precedente appartengono a V(G) tutti i nodi a, b, c, d, e, f.
V(G)={a,b,c,d,e,f}

Il numero dei nodi determina l'ordine del grafo.

Gli archi del grafo

Un arco è una relazione binaria tra due nodi ed è indicato nel seguente modo:

e=(a,b) dove e appartiene a E a appartiene a e b appartiene a e

Dove a e b sono due nodi V del grafo e sono detti estremi dell'arco.

L'arco tra due vertici è detto incidente.

esempio di arco incidente e nodi estremi

Ogni relazione forma una coppia ordinata se è indicata una direzione oppure una coppia non ordinata.

insieme E(G)

Differenza tra coppie ordinate e non ordinate. Nel caso delle coppie non ordinate, le coppie (a,b) e (b,a) indicano lo stesso spigolo del grafo. Viceversa, nel caso delle coppie ordinate le coppie (a,b) e (b,a) indicano un verso differente sullo stesso spigolo, rispettivamente a→b e b→a.

In alternativa, posso indicare un arco scrivendo soltanto i due nodi.

(a,b)

Per indicare l'insieme di tutti gli archi del grafo utilizzo la seguente notazione

E(G) sono tutti gli archi del grafo

Il numero degli archi determina la dimensione del grafo.

Esempio

Nel grafo precedente l'insieme E(G) è composto da tutte le coppie ordinate (a,b) , (a,c), (b,d), (c,d), (c,e), (d,f), (e,f).
l'insieme degli archi del grafo

Posso anche indicare soltanto un sottoinsieme W del grafo.

E(W)

In questo caso l'insieme E(W) comprende tutti gli archi che hanno entrambi gli estremi nel sottoinsieme W.

Esempio

Il sottoinsieme W è composto soltanto dagli archi (a,b), (a,c), (b,d), (c,d).
un esempio di sottoinsieme del grafo

I grafi orientati e non orientati

Esistono due categorie principali di grafi: orientati e non orientati.

  • Grafo orientato. I grafi orientati hanno gli archi con una direzione. In questo caso gli archi sono frecce. Ad esempio, si può andare dal nodo 1 al nodo 2 ma non viceversa, non si può passare dal nodo 2 al nodo 1.
    un esempio di grafo orientato
  • Grafo non orientato. I grafi non orientati hanno gli archi con una relazione biunivoca tra i nodi. In altri termini, il nodo 1 collega il nodo 2 e il nodo 2 collega il nodo 1. Si può scorrere in entrambe le direzioni.
    un esempio di grafo non orientato

La differenza tra grafi orientati e non orientati è importante nello sviluppo dell'algoritmo di calcolo per elaborare la rete dei nodi del grafo, perché la complessità dell'algoritmo è molto diversa.

Le liste e le matrici di adiacenze

Per sviluppare un grafo in un programma informatico si utilizzano due metodi.

  • La lista di adiacenze. I nodi del grafo sono memorizzati in una variabile array. Ogni elemento dell'array indica un nodo del grafo e contiene la lista delle sue connessioni ( archi ).

    un esempio di lista di adiacenza
  • La matrice di adiacenze. In nodi e gli archi sono memorizzati in una matrice quadrata nxn. Dove le n righe indicano i nodi di origine e le n colonne quelli di destinazione. Ogni elemento della matrice indica se i due nodi sono collegati tra loro (1) oppure no (0).

    esempio di lista di adiacene in un grafo non orientato

 


 

Segnalami un errore, un refuso o un suggerimento per migliorare gli appunti

FacebookTwitterLinkedinLinkedin
knowledge base

La teoria dei grafi