Teoria dei grafi e dei giochi
Docente
Prof. Paolo Serafini paolo.serafini@uniud.it http://users.dimi.uniud.it/~paolo.serafini/TGTG****.html
Crediti
6 CFU
Obiettivi
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.
Argomenti
- 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
Bibliografia
Dispense disponibili on-line: http://users.dimi.uniud.it/~paolo.serafini/TGTG.pdf
Modalità d'esame
Esame orale.