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}

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.

Ogni relazione forma una coppia ordinata.

insieme E(G)

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

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



Per scrivere un commento

knowledge base

La teoria dei grafi