Teoria dei grafi e dei giochi - Graph Theory and Game Theory
Docente
- Prof. Paolo Serafini
Indirizzo e-mail
paolo.serafini@uniud.it
Indirizzo Pagina Web Personale
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