INFORMAZIONI SU

Teoria dei grafi e dei giochi - Graph Theory and Game Theory

Programma dell'insegnamento - Corso di laurea Magistrale in Comunicazione multimediale e Tecnologie dell'Informazione

 

Docente

  • Prof. Paolo Serafini

Indirizzo e-mail
paolo.serafini@uniud.it

Indirizzo Pagina Web Personale
Sito Web http://users.dimi.uniud.it/~paolo.serafini/TGTG****.html

 

Crediti

6 CFU

Finalità

Il corso è volto a fornire le basi metodologiche per il successivo corso di Scienza delle reti, per ciò che riguarda la teoria dei grafi e la teoria dei giochi. Della teoria dei grafi si esaminano soprattutto quelle proprietà che emergono quando le dimensioni del grafo sono molto grandi, come avviene in molte reti reali (quali i grafi sociali, internet, web ecc.). Della teoria dei giochi si privilegiano soprattutto gli aspetti relativi agli equilibri dei giochi, sia cooperativi che non cooperativi.

 

Programma


Teoria dei grafi.

  • Definizioni: grafi non orientati, grado di un nodo, sequenza dei gradi, generazione di un grafo dalla sequenza.
  • Isomorfismo fra grafi. Automorfismi.
  • Grafi particolari: grafi completi, grafi bipartiti, alberi, stelle e ruote, grafi planari.
  • Grafi ottenuti da altri grafi: grafo complementare, grafo collassato, sottografi, grafo di linea, prodotto di grafi.
  • Cliques, insiemi indipendenti, insiemi dominanti, coperture di nodi, numero cromatico.
  • Cammini e circuiti, circuiti hamiltoniani, circuiti euleriani, grafi connessi, cammini minimi. Eccentricità di un nodo, raggio e diametro del grafo, taglio in un grafo, alberi e foreste.
  • Grafi orientati: grado esterno e interno di un nodo, grafi aciclici, connessione forte.
  • Matrici: autovalori e autovettori. Matrici di un grafo, matrici di incidenza per grafi non orientati, matrici di incidenza per grafi orientati, matrici d'adiacenza per grafi non orientati. Potenze di matrici d'adiacenza e cammini. Spettro di un grafo: spettro di un grafo completo, spettro di un grafo bipartito. Matrici d'adiacenza per grafi orientati. Matrice Laplaciana. Equazione di diffusione.
  • Catene di Markov. Probabilità stazionaria di una catena.
  • Grafi per famiglie di sottoinsiemi. Rappresentazione come ipergrafi e grafi bipartiti. Proiezioni unimodali, grafo delle cocitazioni, grafo degli accoppiamenti bibliografici.
  • Tagli minimi e massimi flussi. Problema del massimo flusso. Cammini disgiunti negli archi. Cammini disgiunti nei nodi. Taglio minimo di un grafo: algoritmo randomizzato. Tecniche spettrali per min cut e max cut.
  • Modularità: definizione. Matrice di modularità. Massima modularità con tecniche spettrali. Euristica di scambio. Partizione di un grafo in diversi sottografi.
  • Grafi casuali: generalità. Modello G(n,p). Probabilità dei gradi dei nodi. Grafi casuali con gradi prefissati. Funzioni generatrici: introduzione, definizioni principali, esempi. Funzioni generatrici del grado dei nodi. Grado in eccesso. Dimensione delle componenti connesse. Transizione di fase. Componente gigante

Teoria dei Giochi.

  • Definizione di gioco. Forma estesa e forma normale.
  • Giochi a somma zero. Soluzioni del gioco. Giochi a somma non costante. Giochi non cooperativi. Equilibri di Nash. Giochi cooperativi. Negoziati. Giochi a molte persone.

Il piano dettagliato delle lezioni si trova al sito
http://users.dimi.uniud.it/~paolo.serafini/TGTG****.html

 

Prerequisiti (non essenziali)

Algebra lineare, Probabilità

 

Bibliografia

Dispensa disponibile in rete.

 

Modalità d'esame

Orale su appuntamento.

 

Orario di ricevimento

Su appuntamento