Vai al contenuto principale
Oggetto:
Oggetto:

Teoria dei Grafi

Oggetto:

Anno accademico 2007/2008

Codice dell'attività didattica
M8541
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
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

Matematica discreta

Fondamenti di algebra lineare e teoria delle matrici

Geometria I e II

 

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 didattico

Argomento

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:
Ultimo aggiornamento: 19/06/2008 11:13

Non cliccare qui!