Un grafo è una rappresentazione grafica che unisce alcuni nodi attraverso degli archi. Per pensarlo nel mondo reale potremmo immaginare delle città collegate da strade, delle fermate collegate da treni o autobus e così via.
Ci sono versioni facili dei grafi nelle quali ogni collegamento tra i nodi vale uguale e può essere percorso in entrambe le direzioni oppure grafi nei quali posso andare da un nodo all'altro o addirittura grafi in cui gli archi non son tutti uguali. Per esempio su un arco posson passare due persone e sull'altro una sola, oppure un arco è percorso in un minuto e l'altro in due.
Vediamo alcuni esempi per comprendere meglio.
In questo esempio gli archi non sono orientati (o diretti). Quando il problema mi dice un arco le due lettere presenti tra parentesi (che sono i due nodi) sono collegati tra di loro con una linea. Non importa in questo caso l'ordine delle lettere perchè l'arco può essere percorso in entrambe le direzioni.
Questo secondo esempio invece presenta un grafo orientato (o diretto) percui è importante l'ordine delle lettere tra parentesi. La prima rappresenta la partenza e la seconda l'arrivo. Per questo l'arco è rappresentato con una freccia che parte dalla prima lettera e arriva nella seconda
In quest'ultimo esempio gli archi sono anche pesati. Posso immaginarlo come il numero di persone che possono passare contemporaneamente su quell'arco.
Come disegno un grafo?
Per rappresentare un grafo semplicemente aggiungo i nodi e tutti gli archi uno per volta cercando di fare un disegno ampio in cui posso continuare a vedere in modo chiaro gli archi anche quando diventano molti.