Grafi informatici - STEP #13

Il concetto di grafo trova interessanti applicazioni nel campo dell'informatica: è infatti un oggetto discreto che permette di schematizzare una grande varietà di situazioni e di processi e ne consente l'analisi in termini quantitativi e algoritmici.

Nel campo dell'informatica, un esempio concreto in cui questo strumento si pone come mezzo per semplificare dei problemi, sono sicuramente i flow-chart, ovvero formalismi usati per rappresentare algoritmi e definibili mediante grafi (orientati). In questo caso i nodi sono blocchi di istruzioni (che si differenziano per la loro forma), mentre gli archi rappresentano i possibili flussi di esecuzione.

Un grafo informatico contiene:

• un blocco iniziale
• un blocco finale
• un numero finito di blocchi di azione
• un numero finito di blocchi di controllo

Per ogni flow-chart valgono le seguenti condizioni:

1. Ciascun blocco di azione ha una freccia entrante ed una uscente.
2. Ciascun blocco di controllo ha una freccia entrante e due uscenti.
3. Ciascuna freccia entra in un blocco oppure si inserisce in un'altra freccia.
4. Ciascun blocco è raggiungibile dal blocco iniziale.
5. Il blocco finale è raggiungibile dal blocco iniziale.

Più in generale, possiamo supporre che ciascun nodo del grafo sia il supporto di un dato e che ciascun lato dello stesso grafo sia la rappresentazione di una relazione esistente tra i dati contenuti nei nodi che si trovano alle estremità del lato stesso. Da questo punto di vista, un grafo informatico può essere visto come la rappresentazione di una particolare struttura astratta di dati.


Fonte:
https://www.liceotosi.edu.it/inote/wp-content/uploads/sites/18/2018/06/01_Algoritmi_03_Rappresentazione-degli-algoritmi.pdf