Grafi percorsi e reti di trasporto

Cosa rappresenta un grafo?

Un grafo rappresenta un insieme di oggetti connessi tra loro. Gli oggetti sono i vertici e le connessioni sono gli archi.

Vertice → Definizione

Il vertice è un nodo in un grafo. Rappresenta un'entità, come una città o un punto di interesse.

Arco → Definizione

L'arco è una connessione tra due vertici. Può essere diretto o indiretto a seconda della direzione.

Grafi orientati vs Grafi non orientati

Nei grafi orientati, gli archi hanno una direzione. Nei grafi non orientati, gli archi sono bidirezionali.

Esempio di grafo pratico

Una mappa stradale è un grafo: le città sono vertici e le strade sono archi.

Cosa rappresenta il grado di un vertice?

Il grado di un vertice è il numero di archi incidenti su di esso. Indica la connessione.

Ciclo in un grafo → Vero o falso?

Vero. Un ciclo è un percorso che inizia e finisce nello stesso vertice.

Esempio di utilizzo dei grafi

Ottimizzazione di consegne. Un grafo rappresenta i percorsi e le distanze tra i punti di consegna.

Cammino semplice → Definizione

Un cammino semplice è un percorso che non visita lo stesso vertice più di una volta.

Come si calcola la distanza tra due vertici?

Utilizzando la somma dei pesi degli archi che collegano i vertici nel cammino scelto.

Esempio pratico: calcolo percorso

Se A-B costa 5€ e B-C costa 3€, il costo A-C via B è 8€.

Grafo completo → Definizione

Un grafo completo è un grafo in cui ogni coppia di vertici è connessa da un arco.

Cosa sono i pesi degli archi?

I pesi rappresentano costi o distanze associate agli archi. Utilizzati per ottimizzare percorsi.

Esempio di grafo pesato

Un grafo stradale dove ogni arco ha un peso corrispondente alla distanza in chilometri.

Differenza tra sottografo e grafo

Un sottografo contiene alcuni vertici e archi del grafo originale, mantenendo la connessione.

Componenti connesse → Definizione

Le componenti connesse sono sottogruppi di vertici in cui ogni vertice è raggiungibile da un altro.

Tipi di percorsi nei grafi

1. Percorso semplice: non ripete vertici. 2. Percorso chiuso: inizia e finisce nello stesso vertice. 3. Ciclo: percorso chiuso senza ripetizioni.

Ciclo e percorso: differenza

Un ciclo ritorna al vertice di partenza, un percorso può non farlo. Esempio: ciclo (A-B-C-A), percorso (A-B-C-D).

Sommario utilizzo cicli

- Pianificazione itinerari. - Ottimizzazione risorse. - Analisi reti di comunicazione.

I grafi orientati: caratteristiche

I grafi orientati hanno archi direzionali. Usati per modellare flussi unidirezionali, come strade a senso unico.

Ciclo di Hamilton: esistenza?

Vero o falso? Vero. Un ciclo di Hamilton visita ogni vertice una sola volta e torna al punto di partenza.

Esempio di percorso ottimale

Un camion deve percorrere 100 km per consegnare merce. Minimizzare il costo considerando $\displaystyle 0.5€/km$.

Utilizzo di percorsi nei problemi di rete

- Massimizzare efficienza. - Minimizzare costi di trasporto. - Pianificare itinerari per ridurre tempo.

Cicli e capacità in reti

Cicli critici possono influenzare la capacità massima di trasporto. Maggiore capacità implica minori ritardi.

Percorsi e flusso massimo: relazione

Un percorso di flusso massimo permette di determinare il quantitativo massimo di materiale trasportabile in una rete.

Esempio di ciclo e costo

Un ciclo che attraversa 5 archi con costo di $\displaystyle 2€$ ciascuno avrà un costo totale di $\displaystyle 10€$.

Ciclo di Euler: definizione

Un ciclo di Euler attraversa ogni arco esattamente una volta e torna al punto di partenza. Esiste solo in grafi con tutti i vertici di grado pari.

Compito: calcolare un percorso

Trova il percorso più breve da Roma a Milano (600 km) con un costo di $\displaystyle 0.6€/km$. Costo totale: $\displaystyle 360€$.

Cosa rappresenta un grafo in un problema di trasporto?

Un grafo rappresenta un insieme di nodi (località) e archi (strade) utilizzati per analizzare percorsi e costi di trasporto.

Qual è la formula per calcolare il costo totale di un percorso?

Costo totale = somma dei costi degli archi lungo il percorso. Esempio: costo = 10€ + 20€ + 15€ = 45€.

Vero o falso: I nodi rappresentano solo le fermate in un grafo.

Falso. I nodi possono rappresentare anche centri di distribuzione o incroci importanti.

Confronta i costi di due percorsi: A-B-C e A-D-C.

Percorso A-B-C = 50€, A-D-C = 40€. Scegli il percorso A-D-C per risparmiare 10€.

Completa: Il costo per km di un trasporto è di ___€.

Il costo per km di un trasporto è di 0,50€.

Quali fattori influenzano i costi di trasporto?

- Distanza totale - Tipo di mezzo - Costi operativi - Tasse e pedaggi

Esempio di calcolo: percorri 100 km a 0,75€/km.

Costo totale = 100 km × 0,75€/km = 75€.

Cosa indica il grado di un nodo in una rete di trasporto?

Il grado indica il numero di archi che connettono il nodo, riflettendo l'importanza della località nella rete.

Vero o falso: Le reti di trasporto sono sempre bidirezionali.

Falso. Alcuni archi possono essere unidirezionali, come le strade a senso unico.

Definisci il termine 'giro' in un grafo di trasporto.

Un giro è un percorso che inizia e termina nello stesso nodo, senza ripetere archi.

Cause principali di costi elevati nel trasporto?

- Congestione del traffico - Distanze lunghe - Manutenzione dei veicoli

Qual è l'obiettivo principale nella pianificazione delle reti di trasporto?

Ottimizzare i percorsi per ridurre i costi e migliorare l'efficienza del trasporto.

Qual è l'applicazione dei grafi nei trasporti?

I grafi modellano le reti stradali, ferroviarie e aeree. Permettono di ottimizzare i percorsi per ridurre il tempo di viaggio e i costi.

Vero o falso: i grafi aiutano a pianificare viaggi efficienti.

Vero. I grafi sono fondamentali per trovare il percorso più breve e analizzare i tempi di percorrenza.

Grafi → reti elettriche.

- Monitoraggio del carico - Ottimizzazione della distribuzione - Prevenzione dei guasti

Esempio di utilizzo dei grafi nei negozi?

Un supermercato usa grafi per ottimizzare la disposizione degli scaffali. Riduce il tempo di ricerca e migliora l'esperienza del cliente.

Quale algoritmo per il calcolo del percorso più breve?

L'algoritmo di Dijkstra. Utilizza pesi per rappresentare distanze o costi e trova il percorso ottimale da un nodo a tutti gli altri.

Utilizzo dei grafi nella gestione dei rifiuti?

I grafi aiutano a pianificare i percorsi dei camion per raccogliere rifiuti in modo efficiente, riducendo costi e impatto ambientale.

Riempire il vuoto: i grafi possono modellare ____ di comunicazione.

reti. Utilizzati per ottimizzare le connessioni tra dispositivi e migliorare la velocità di trasmissione dei dati.

Differenza tra un grafo orientato e uno non orientato?

Un grafo orientato ha archi con direzione, mentre un grafo non orientato non ha direzioni. Esempio: strade a senso unico (orientato) vs strade a doppio senso (non orientato).