Teoria dei grafi/2006-2007

Informazioni generali

Teoria dei grafi è un insegnamento complementare dei Corsi di Laurea del DSI/DICo.

Docente

Ottavio Mario D'Antona

Orari delle lezioni

• Lunedì 17.30 - 19.30
• Giovedì 17.30 - 19.30
• Venerdì 16.30 - 18.30

in Auletta 5 (via Comelico).

Orario di ricevimento studenti

Lunedì 12.00 - 14.00 in P117.

Sito del corso

http://homes.dico.unimi.it/~dantona/tg/

Materiale didattico

• "Introduzione alla matematica discreta" del docente (disponibile in biblioteca)

Modalità d'esame

• Orale o tesina su uno degli argomenti del corso

Diario del corso

Lezione del 2 Ottobre 2006

• introduzione al corso e alla combinatoria

Lezione del 5 Ottobre 2006

• partizione di un insieme
• numeri di Stirling di seconda specie S(n,k): $S(n,k)=S(n-1,k-1)+kS(n-1,k)$
• funzione generatrice di una successione di numeri
  • funzione generatrice esponenziale: $F(x)=\sum _{{n\geq 0}}a_{n}{\frac {x^{n}}{n!}}$
  • funzione generatrice ordinaria o geometrica: $F(x)=\sum _{{n\geq 0}}a_{n}x^{n}$

Lezione del 6 Ottobre 2006

• polinomi: relazioni tra base, radici e coefficienti
• funzioni simmetriche
  • elementari
  • omogenee complete
• successione persistente di polinomi

Lezione del 9 Ottobre 2006

• relazione
• [[::it:Relazione di equivalenza|relazione di equivalenza]]
• relazione d'ordine parziale
  • diagramma di Hasse
  • insieme parzialmente ordinato (IPO o POSet)
  • funzione di Möbius

Lezione del 12 Ottobre 2006

• minima limitazione superiore e massima limitazione inferiore di un IPO
• reticolo
• reticolo di partizioni
• polinomio caratteristico di un reticolo
• teoria delle inversioni di Möbius

Lezione del 13 Ottobre 2006

• funzioni tra alberi radicati open maps (preservano ordine e downset)
• mappatura tra catene
• mappatura da alberi a catene
• mappatura da catene ad alberi
• leaf theorem

Lezione del 16 Ottobre 2006

• partizioni di un albero
• ordinamento dei blocchi in una partizione
• albero dei blocchi
• numero funzioni totali e di iniezioni tra due insiemi