Insegnamento mutuato da: B018796 - TEORIA DEI GRAFI E COMBINATORIA Laurea Magistrale in MATEMATICA Curriculum APPLICATIVO
Lingua Insegnamento
italiano
Contenuto del corso
Teoria dei Grafi, soprattutto grafi semplici non orientati. Nozioni di Base e alcune nozioni avanzate di teoria dei grafi. Grafi Planari, Grafi euleriani. Grafi hamiltoniani.
Combinatoria classica.
Disegni e loro parametri. Piani proiettivi finiti. Teoremi fondamentali di teoria dei grafi e Combinatoria. Alcuni problemi aperti e congetture importanti della Teoria dei grafi e della Combinatoria
Chartrand-Lesniak-
Zhang "Graphs and Digraphs" Fifth Edition
Obiettivi Formativi
Conoscere le nozioni basilari della Combinatoria e della Teoria dei Grafi.
Essere in grado di dimostrare semplici proposizioni riguardanti grafi, disegni ed altre strutture combinatorie
Essere in grado di applicare le idee della Combinatoria e della Teoria dei Grafi a problemi di vario tipo
Prerequisiti
Prime nozioni di Teoria dei Gruppi ed Algebra
(Algebra I ed Algebra II)
Metodi Didattici
Lezioni ed esercitazioni in classe. Partecipazio- ne degli studenti alla scoperta e dimostrazio-
ne di Concetti e Proposizioni matematici Discussioni
con gli studenti con prove scritte
Modalità di verifica apprendimento
Prove scritte in itinere e
prova scritta finale
Programma del corso
Definizione di Grafo
Definizione di Gruppo
Gruppo di automorfismi
di un grafo
Grafi transitivi sui vertici
Esempi ed Esercizi
Matrice di adiacenza di un grafo
Autovalori di un grafo
Proposizioni basilari su autovalori e cicli in un grafo
Grafi Planari. Grafi euleriani. Grafi hamiltoniani.
Problemi aperti impor- tanti della Teoria dei Grafi:
-- La congettura di Lovasz
-- La congettura della Ricostruzione
-- La congettura dei tre sentieri di lunghezza massima
-- Congettura di Lauri sui vertici pseudo-simili
Definizione di Disegno
Paranetri di un disegno
Proposizioni basilari sui disegni simmetrici bilanciati
Piani proiettivi finiti
Congettura sull'ordine di un piano proiettivo
Teorema di Bruck and Ryser
Congettura di Chvatal