10: Allocazione dinamica della memoria Vers. 9.1 – Ottobre 2025
3) Orientando ed eliminando opportunamente uno o più archi del grafo
A
F
C G
B E
L
I
D H
In questo caso è stato sia orientato opportunamente l’ arco che congiunge i nodi B ed A, sia eliminato l’ arco che unisce i nodi L ed I.
DEF. Un grafo G si definisce pesato se ad suo arco viene associato un valore detto peso
Esempio di grafo G connesso e pesato
Lecce
DOMANDA: A che servono i grafi?
I grafi possono essere visti come modelli in grado di rendere possibile l’ astrazione su alcuni aspetti del mondo reale ossia sono in grado di rappresentare un sistema“ semplificato” eventualmente presente nella realtà.
Esempio: Per rappresentare un sistema di trasporti ci si può servire di un grafo G pesato con le
località da servire( che possono essere rappresentate come nodi), le linee di comunicazione tra le località( che possono essere rappresentate come archi) e la distanza chilometrica tra due località( che può essere vista come peso).
Esiste in informatica una classe di problemi legati al percorso minimo che unisce tutti i nodi di un grafo G ossia il cammino semplice con peso minimo che congiunge tutti i nodi di un grafo G.
Un grafo è particolarmente adatto a rappresentare anche automi, reti di trasporto, reti elettriche, reti dati, etc.
Autore: Rio Chierego( email: riochierego @ libero. it- sito web: www. riochierego. it) Pag. 45