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. |
|
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.
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).
Esercizi: testo e soluzione, testo e soluzione, testo e soluzione, testo e soluzione, testo e soluzione.