Antonio Sforza » 17.Ottimizzazione su rete: Introduzione alla Teoria dei Grafi

Schema della lezione

In questa lezione si introducono le definizioni fondamentali di teoria dei grafi necessarie per formulare e risolvere i problemi di ottimizzazione su rete che saranno descritti nelle lezioni successive.

Nell’ambito dei grafi orientati si forniscono le definizioni di percorso e circuito e si introducono particolari tipi di grafi orientati. Vengono esposte inoltre le principali forme di rappresentazione di un grafo, corrispondenti a diverse strutture dati, di tipo matriciale o vettoriale.

Si descrive poi la procedura di visita di un grafo e si introducono infine i parametri numerici fondamentali necessari per la definizione dei problemi di ottimizzazione su rete.

Grafo connesso

Grafo non connesso

Grafi

Grafo completo G

Grafo completo G_p

Grafo a livelli

Grafo bipartito

Arborescenza

Arborescenza

Arborescenza biforcante

Grafi orientati e non orientati

Grafo orientato G

Grafo non orientato G'

Albero

Grafo-Densità

Grafo di riferimento

Grafo di riferimento

Matrice di adiacenza vertice-vertice

Grafo di riferimento

Grafo di riferimento

Matrice di incidenza vertice-arco

Grafo di riferimento

Grafo di riferimento

Liste P-S

Liste P-S sparse

Grafo di riferimento

Grafo di riferimento

Liste con puntatori

Grafo orientato

Grafo orientato

Albero di visita in larghezza

Grafo orientato

Grafo orientato

Albero di visita in profondità

Disuguaglianza triangolare e costo di percorso

c_ij ≤ c_ik + c_kj

∀ij ∈A, ∀ k ∈V, k ≠ i, j

C_p,od = ∑_{ij ∈p cij}

∀ p ∈P_od

Reti

R = (V, A, W )  in cui V ed A assumono i significati noti e W è l’insieme dei pesi sui vertici.

R = (V, A, C ) in cui C è l’insieme dei costi di spostamento sugli archi.

R = (V, A, W, C )