10 : Allocazione dinamica della memoria Vers . 9.0 – Ottobre 2024
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