- Oggetto:
- Oggetto:
Teoria dei Grafi - a.a. 2008/09
- Oggetto:
Anno accademico 2008/2009
- Codice dell'attività didattica
- MFN0177
- Docente
- Prof. Marco Burzio (Titolare del corso)
- Corso di studi
- Laurea in Matematica
- Anno
- 3° anno
- Periodo didattico
- Secondo semestre
- Tipologia
- A scelta dello studente
- Crediti/Valenza
- 5
- SSD dell'attività didattica
- MAT/02 - algebra
- Mutuato da
- 5CFU Ambito G
- Oggetto:
Sommario insegnamento
- Oggetto:
Obiettivi formativi
La teoria dei grafi, pur essendo una branca della matematica pura, ha numerose applicazioni nei più disparati settori della scienza e della tecnologia (ottimizzazione dei trasporti e delle risorse, architettura dei circuiti stampati, ecc.).
Il corso si propone di fornire agli studenti le conoscenze di base della teoria dei grafi e di renderli in grado di studiare e risolvere le problematiche collegate anche utilizzando gli algoritmi introdotti durante il corso.- Oggetto:
Risultati dell'apprendimento attesi
L'allievo dovrà ottenere padronanza con gli argomenti, le tecniche e gli algoritmi introdotti durante il corso. In particolare dovrà dimostrare di saper risolvere, utilizzando le tecniche proprie della teoria dei grafi, vari problemi di tipo combinatorio che nascono tanto in ambito teorico quanto nelle applicazioni. Dovrà dimostrare di saper maneggiare concetti quali la traversabilità, la planarità, le diverse colorazioni ed etichettatura dei grafi.- Oggetto:
Programma
Pre-requisiti in ingresso e competenze minime in uscita
Pre-requisiti (in ingresso)
Insegnamenti fornitori
Fondamenti di combinatorica
Algebra
Fondamenti di algebra lineare e teoria delle matrici
Geometria I
Competenze minime (in uscita)
Insegnamenti fruitori
Argomenti di base della teoria dei grafi.
Principali tecniche ed algoritmi della teoria dei grafi.
La maggior parte dei corsi di Istituzione della LM, in particolare: Istituzioni di Algebra, Istituzioni di Logica Matematica.
Programma, articolazione e carico didatticoArgomento
Ore
Lezione
Ore
Esercitazione
Totale Ore di Carico Didattico
Grafi. Sottografi. Operazioni. Successione dei gradi.
4
2
6
Connessione. Grafi euleriani ed hamiltoniani.
8
4
12
Matrici. Alberi. Alberi ricoprenti.
6
2
8
Grafi planari.
5
3
8
Colorazioni
3
2
5
Digrafi. Networks. Flussi.
4
2
6
Totale
30
15
45
Grafi e sottografi: grafi, sottografi, grafi speciali, operazioni sui grafi, successioni dei gradi.
Grafi connessi e sconnessi: cammini e cicli, complemento di un grafo e grafi autocomplementari, vertici separanti e ponti, grafi euleriani, grafi hamiltoniani, blocchi.
Matrici e alberi: grafi e matrici, alberi, il numero degli alberi non identici, alberi ricoprenti e teorema degli alberi e delle matrici.
Grafi planari e non planari: la formula di Eulero, condizioni algebriche necessarie planarità, grafi planari e poliedri, omeomorfismo, caratterizzazione dei grafi planari.
Colorazioni sui grafi: il numero cromatico, l'algoritmo k-colorabile, il teorema dei quattro colori, il polinomio cromatico, colorazioni sui lati.
Digrafi e networks: digrafi e tornei, networks e cammini critici, flussi e tagli.Testi consigliati e bibliografia
- Oggetto:
- M. BEHZAD - G. CHARTRAND - L. LESNIAK-FOSTER, Graphs & Digraphs, Prindle, Weber & Schmidt.
S.B. MAURER - A. RALSTON - Discrete Algorithmic Mathematics, Addison-Wesley.
Dispense disponibili presso il Centro Stampa e in rete. - Oggetto:
Note
Prova orale preceduta, nello stesso giorno, da una breve prova scritta.- Oggetto: