Primi elementi della teoria dei grafi

Che cosa è un grafo

Un grafo è una figura del piano (o dello spazio) costituita da un insieme di punti detti vertici o nodi e da un insieme di linee dette spigoli o archi che uniscono coppie di nodi o un nodo con se stesso.

In generale un nodo rappresenta un oggetto qualsiasi e un arco rappresenta una relazione tra i due oggetti che unisce. Con questa concezione un grafo diventa un potente strumento per rappresentare visivamente un qualsiasi insieme di oggetti e le loro reciproche relazioni e quindi un modello per rappresentare in modo semplice una qualsiasi situazione reale. Ad esempio, se ai nodi diamo il significato di città e all'arco il significato di strada che unisce due città ecco che il grafo può rappresentare la mappa di una rete stradale tra varie città.

Se invece al nodo diamo il significato di stazione e all'arco il significato di collegamento ferroviario tra due stazioni il grafo può rappresentare la mappa di una rete metropolitana.

Se invece al nodo diamo il significato di atomo e all'arco il significato di legame tra due atomi il grafo può rappresentare la struttura di una molecola.

Uno stesso grafo può essere interpretato in più modi perchè esistono diverse situazioni concrete che sono traducibili con un medesimo grafo e quindi nell'interpretazione di un grafo è necessario conoscere il significato attribuito ai nodi e agli archi.

Per esperienza sappiamo che un grafo che rappresenta la mappa di una metropolitana non ci fornisce informazioni sulle distanze tra le varie stazioni o la forma esatta del tragitto tra due stazioni eppure è utile perchè ci permette di capire in che ordine si succedono le stazioni, se esiste un collegamento diretto tra due stazioni, se tale collegamento è unico, se fra i vari collegamenti possibili tra due stazioni c'è nè uno che ha meno fermate intermedie. Da questo esempio si intuisce che in un grafo non è importante nè la posizione occupata dai nodi nè la lunghezza o la forma degli spigoli che possono essere rettilinei o archi di curva, ciò che interessa è visualizzare le connessioni tra i nodi. Possiamo immaginare gli spigoli di un grafo come sottili fili elastici e i vertici come delle piccole sfere che possiamo muovere come si vuole senza però provocare tagli o strappi ai fili elastici. Ad esempio, i due grafi in figura formiscono le stesse informazioni: hanno lo stesso numero di vertici, lo stesso numero di spigoli e le stesse connessione tra vertici corrispondenti c'è quindi una corrispondenza biunivoca tra i rispettivi vertici e i rispettivi spigoli. Se due grafi non hanno la stessa forma ma hanno le stesse caratteristiche e quindi forniscono le stesse informazioni si dicono che sono isomorfi

In un grafo una stessa coppia di vertici può avere più di uno spigolo che li unisce, in questo caso si dice che il grafo ha spigoli multipli o paralleli, ad esempio, in un grafo che rappresenta una mappa stradale questo potrebbe corrispondere a due città collegate tra loro con più strade diverse oppure in un grafo che rappresenta un torneo di calcio questo potrebbe corrispondere alle due partite disputate tra due squadre una in casa e l'altra fuori casa, oppure in un grafo che rappresenta una molecola questo potrebbe corrispondere a due atomi uniti con un doppio legame oppure uniti con un triplo legame.

In un grafo un vertice potrebbe essere collegato con se stesso in questo caso lo spigolo viene detto cappio, ad esempio in un grafo che rappresenta una mappa stradale questo potrebbe corrispondere a un parcheggio oppure a una pista circolare.

In genere, c'è l'abitudine di distinguere tre tipi di grafi: semplici, multigrafi e pseudografi. Un grafo è semplice se non ha cappi e non c'è mai più di uno spigolo che congiunge una data coppia di nodi, è multigrafo se contiene spigoli multipli, è pseudografo se contiene cappi.

Da questi semplici esempi si intuisce che i grafi sono importanti perchè permettono di modellare problemi reali in modo naturale. Ad esempio:

• Reti di trasporto: strade, ferrovie, metropolitane.
• Reti informatiche: Internet, reti locali, topologie di comunicazione.
• Reti sociali: connessioni tra persone, gruppi, comunità.
• Algoritmi: ricerca del percorso minimo, visita di nodi, ottimizzazione.
• Biologia: reti metaboliche, interazioni tra proteine.