Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

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

Grafo completo Gp

Grafo completo Gp


Grafo a livelli


Grafo bipartito


Arborescenza

Arborescenza

Arborescenza

Arborescenza biforcante

Arborescenza biforcante


Grafi orientati e non orientati

Grafo orientato G

Grafo orientato G

Grafo non orientato G’

Grafo non orientato G'

Albero

Albero


Grafo-Densità


Grafo di riferimento

Grafo di riferimento

Grafo di riferimento

Matrice di adiacenza vertice-vertice

Matrice di adiacenza vertice-vertice


Grafo di riferimento

Grafo di riferimento

Grafo di riferimento

Matrice di incidenza vertice-arco

Matrice di incidenza vertice-arco


Grafo di riferimento

Grafo di riferimento

Grafo di riferimento

Liste P-S

Liste P-S

Liste P-S sparse

Liste P-S sparse


Grafo di riferimento

Grafo di riferimento

Grafo di riferimento

Liste con puntatori

Liste con puntatori


Grafo orientato

Grafo orientato

Grafo orientato

Albero di visita in larghezza

Albero di visita in larghezza


Grafo orientato

Grafo orientato

Grafo orientato

Albero di visita in profondità

Albero di visita in profondità


Disuguaglianza triangolare e costo di percorso

cij cik + ckj

ij A, k V, k ≠ i, j

Cp,od = ij p cij

p Pod

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 )

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion