Grafi
Cos'è un grafo
Un grafo G=(V,E) è una struttura relazionale composta da un insieme dei vertici o vertex V={1, 2, …, n) e un insieme di coppie di vertici (i,j) detti spigoli o edges E={ e1, e2, … , em }.
Per rappresentare il grafo indico i vertici con dei cerchi.
All'interno di ogni cerchio scrivo l'etichetta identificativa del vertice. Può essere un numero o una lettera.
Gli spigoli, invece, sono le linee che collegano i vincoli.
Un esempio pratico
Questo grafo è composto da 4 vertici e 5 spigoli.
L'insieme dei vertici V del grafo G è composto da quattro vertici.
$$ V(G) = { 1,2,3,4 } $$
L'insieme degli spigoli E del grafo G è composto da cinque spigoli
$$ E(G) = { (1.2),(1,3),(1,4),(2.4),(3,4) } $$
Ogni spigolo (linea) è una coppia ordinata di vertici detti estremi.
Il primo elemento indica il vertice di partenza, il secondo elemento il vertice di destinazione.
Nota. Non essendoci un verso, ogni spigolo permette lo spostamento in entrambe le direzioni. Pertanto, lo spigolo (a,b) è uguale allo spigolo (b,a). Ad esempio, gli spigoli (1,2) e (2,1) sono lo stesso spigolo. E via dicendo.
Esempio 2
In alternativa posso rappresentare il grafo anche in questa forma più sintetica.
In questa rappresentazione i vertici (vertices) sono dei punti e gli spigoli (edges) sono linee.
Ogni vertice è etichettato con una lettera maiuscola.
Esempio 3
Questo grafo è composto da 5 vertici e 8 spigoli.
L'intersezione dello spigolo (A,D) e (B,C) non è un vertice perché non c'è alcun punto (vertice).
Questo vuol dire che i due spigoli (A,D) e (B,C) non sono collegati tra loro.
Lo spigolo (A,D) passa sopra (o sotto) l'altro spigolo (B,C) come un cavalcavia sull'autostrada.
Nota. Per rappresentare questa situazione posso anche far passare il vertice senza intersezioni. Tuttavia, questa rappresentazione non è facile da costruire quando gli spigoli sono molti. Inoltre, si perde il concetto visivo di lunghezza dello spigolo.
Il grado di un vertice
Il grado di un vertice indica il numero di spigoli collegati al vertice stesso.
Ad esempio, il vertice A è di grado 3 perché ha tre spigoli.
Il vertice E è di grado 2 perché ha due spigoli.
Nota. Questi esempi sono detti grafi semplici perché non contengono spigoli multipli o loop.
Gli spigoli multipli
Gli spigoli multipli (multiple edges) sono spigoli che hanno in comune gli stessi vertici agli estremi.
Ad esempio, due spigoli collegano i vertici A e B
Questi due spigoli sono spigoli multipli.
I loop
Un loop è uno spigolo che collega lo stesso vertice.
Ad esempio, in questo grafo il vertice A ha un loop.
Lo spigolo ha lo stesso vertice (A) in entrambi gli estremi.
Il cammino sul grafo può procedere all'infinito restando sullo stesso vertice.
I digrafi
I digrafi (digraphs o directed graphs) sono grafi direzionali in cui gli spigoli hanno un verso di percorrenza.
Ad esempio, questo grafo è un digrafo.
Il grafo consente lo spostamento dal vertice A al vertice B ma non il contrario.
Nel caso dei digrafi gli spigoli direzionali (directed edges) sono anche detti archi (arc) e mentre i vertici sono detti nodi.
La differenza tra cammini, percorsi e cicli
In un grafo un cammino (walk) è una sequenza di vertici connessi da spigoli o archi.
Ad esempio, la sequenza A→B→C→D→E→C è un cammino.
Un percorso (path) è una sequenza di vertici connessi tra loro spigoli o archi in cui nessun vertice appare più di una volta.
Ad esempio, la sequenza A→B→C→D→E→C è un percorso.
Il ciclo (cycle) è un cammino in cui il vertice iniziale e finale della sequenza sono lo stesso vertice e nessun altro vertice della sequenza appare più di una volta.
Ad esempio, la sequenza A→B→C→A è un ciclo.
E così via.
