Grafi

I grafi sono diagrammi costituiti da oggetti e da linee che collegano alcuni di essi; gli oggetti vengono chiamati nodi, le linee archi.     Se gli archi sono muniti di un verso, il grafo viene chiamato orientato; in questo caso gli archi possono essere chiamati anche frecce. Gli eventuali nodi in cui non arrivano frecce vengono detti nodi iniziali, quelli da cui non partono frecce vengono detti nodi finali. Un insieme di archi che collega un nodo con sé stesso passando attraverso altri nodi si chiama maglia. Una successione di nodi collegati l'uno al successivo da un arco si chiama cammino.

grafo grafo orientato

    Anche i diagrammi di flusso sono una specie di grafi.

  Particolarmente usati sono i grafi ad albero. Si tratta di grafi orientati tali che:
(1)  esiste un unico nodo iniziale, dal nodo iniziale possono essere raggiunti seguendo le frecce tutti gli altri nodi, in ciascuno di questi nodi entra una sola freccia (in questi casi il nodo da cui parte una freccia si dice padre del nodo in cui la freccia arriva, che dicesi nodo figlio);
  oppure tali che:
(2)  esiste un unico nodo finale, il nodo finale può essere raggiunto da tutti gli altri nodi, da ciascuno di questi parte una sola freccia.

[Spesso si evita di tracciare la punta delle frecce. Allora in genere si considerano nodi iniziali quelli in alto, se i grafi sono disposti verticalmente, o quelli a sinistra, se i grafi sono disposti orizzontalmente]

  I grafi ad albero sono usati, tra l'altro, per rappresentare la struttura dei termini: il grafo sotto a sinistra è del tipo (1) e analizza il termine (5 + 3) · (5 - 3); il grafo a destra è del tipo (2) e illustra come si puì costruire il termine (5 + 3) · (5 - 3).

  Molto usati sono anche i grafi di flusso; così vengono chiamati i grafi orientati quando le frecce sono usate per rappresentare flussi di "cose" (denaro, beni, persone, ...) da un nodo all'altro.
    Ad esempio il grafo di flusso parzialmente riprodotto sotto illustra il flusso degli alunni di una certa scuola superiore tra il 1997 e il 1998 (supponiamo che non vi siano scambi con le altre scuole superiori, e, in particolare, che i nuovi arrivati provengano solo dalla scuola media).

[il  nodo SM rappresenta gli alunni che nel 97/98 erano iscritti alla scuola media inferiore e che nel 98/99 si sono iscritti in questa scuola, il nodo alla sua destra rappresenta gli alunni che nel 97/98 erano iscritti alla classe 1a, quello ancora a destra rappresenta gli alunni che nel 97/98 erano iscritti alla 2a, ...; sotto sono rappresentati gli alunni che erano iscritti in 1a, 2a, ... nel 98/99; il nodo ABB indica coloro che hanno abbandonato la scuola: iscritti nel 97/98 che, senza essersi diplomati, non si sono riiscritti nel 98/99]

    I valori scritti nei riquadri relativi ai vari nodi sono la somma delle misure delle "cose" che escono da essi (qui le misure sono quantità di alunni): 181 = 36 + 54 + 91, ovvero la somma delle misure delle "cose" che entrano: 118 + 36 = 154.
    I grafi di flusso sono spesso più comodi da usare delle rappresentazioni mediante equazioni. Ad esempio nel caso in cui della situazione precedente si conoscessero solo le informazioni rappresentate nel grafo (1) sotto a sinistra e si volesse sapere quanti hanno abbandonato tra la classe I e la classe II, è facile arrivare alla risposta passando al grafo (2) (che esprime il fatto che occorre innanzi tutto trovare il valore di quanti ripetono la prima, ossia di quanti si aggiungono a 118 per formare 154) e poi al grafo (3) (c'è da trovare quanti di 181 rimangono se se ne tolgono 36 e 91). Usando equazioni il procedimento sarebbe meno intuitivo.

Per un esempio di impiego dei grafi non orientati si pensi alla situazione illustrata dal grafo a fianco, in cui i nodi rappresentano località, gli archi rappresentano strade (a doppio senso) e i numeri le lunghezze (in km) di queste.     Questo modello matematico può essere considerato uno spazio:  possiamo chiamare punti i nodi del grafo e distanza tra x e y la lunghezza del percorso più breve per andare da x a y.     Volendo fare a meno della rappresentazione con pallini e linee posso descrivere questo spazio come l'insieme che ha per elementi A, B, C, D ed E ed è dotato della funzione distanza definita dalla tabella a fianco.

x  y  A   B   C   D   E  A  0 2 3 3 1 B  2 0 1 5 3 C  3 1 0 5 3 D  3 5 5 0 2 E  1 3 3 2 0