B018796 - TEORIA DEI GRAFI E COMBINATORIA

Teoria dei Grafi e Combinatoria.
Algebra lineare e Teoria dei Gruppi applicata alla teoria dei grafi. Problemi aperti rilevanti della Teoria dei Grafi

Chartrand-Lesniak
Grafi e Digrafi
Seconda edizione

Biggs
Teoria Algebrica dei Grafi Seconda ed

Ottenere una conoscenza di base e di livello intermedio
della Teoria dei Grafi e della Combinatoria.
Facilita' nell'uso della
induzione e di altre tecniche di dimostrazione tipiche della teoria dei grafi e della Combinatoria

Conoscenze di base di algebra e teoria degli insiemi come quelle acquisite nei corsi di Algebra I ed algebra II

Lezioni che espongono i teoremi e le loro dimostrazioni seguite da discussioni in classe relative a possibili variazioni e miglioramenti degli enunciati e delle loro dimostrazioni. Produzione di alcuni compiti a casa per la verifica del corretto apprendimento

La frequenza alle lezioni contribuisce al calcolo del voto finale nella misura del 20% circa

Quattro verifiche intermedie scritte.
Colloquio orale finale
e breve presentazione di un teorema da parte dello studente

In base alla reattivita' degli studenti, si tratteranno argomenti di carattere piu' semplice o avanzato. Per ciascun argomento, oltre alle definizioni e teoremi basilari, verranno presentati ed illustrati problemi a tutt'oggi non soluti. Compiti a casa e lavoro di classe verranno anche dedicati alla ricerca di possibili nuove idee di dimostrazione. Lo scopo di tale attivita' e' quello di sviluppare l'attitudine alla ricerca matematica individuale. Tra i diversi argomenti da trattare nel corso, i seguenti saranno certamente inclusi:
-- Autovalori di grafi
-- Formula di Cauchy-Burnside-Frobenius per il conteggio del numero di classi di equivalenza
-- Grafi planari, euleriani, hamiltoniani.
-- Ricostruzione dei grafi.
-- Colorazioni e teorema di Vizing
-- Condizione di Planarita' di Kuratowski.
-- Congettura della Ricostruzione.
-- Intersezione di sentieri di lunghezza massima in grafi connessi
-- Alberi, loro caratterizzazioni e teoremi basilari su di essi