Operazioni in un insieme e loro possibili proprietà. La nozione di “monoide”, “semigruppo”,
“gruppo”. Esempi. Chiusura rispetto a un’operazione. Sottomonoidi, sottosemigruppi, sottogruppi.
Sottogruppo generato da un sottoinsieme. Gruppi ciclici. Sottogruppi dei gruppi ciclici. Classi laterali.
Teorema di Lagrange. Sottogruppi normali. Criterio di normalità. Gruppo quoziente.
Nucleo di un omomorfismo. Primo teorema di omomorfismo. Prodotto di sottogruppi. Prodotto diretto. Normalizzante.
Secondo teorema di omomorfismo. Teorema di corrispondenza.
Permutazioni. Gruppi di permutazioni. Il gruppo simmetrico Sn e il gruppo alterno An.
Ordine di Sn ed An. Decomposizione di una permutazione in cicli disgiunti
(con dimostrazione grafica).
Struttura di una permutazione. Calcolo del numero di permutazioni aventi una data struttura.
Trasposizioni. Decomposizione di una permutazione in trasposizioni. Parità.
Rappresentazioni di un gruppo come gruppo di permutazioni. Teorema di Cayley. Orbite. Punti fissi.
Equazione delle orbite. Stabilizzatori. Applicazioni dell’equazione delle orbite.
Centralizzante. Relazione tra ordine del centralizzante e ordine della classe di coniugio.
Alcune proprietà dei p-gruppi. Teoremi di Sylow, generalizzazioni ed applicazioni:
quali sono i gruppi che hanno un numero assegnato di elementi?
Questa parte del programma corrisponde al contenuto degli appunti “informali” di Teoria dei Gruppi
(redatti dal docente e dal dott. Virgilio Pannone) consegnati brevi manu agli studenti.
Definizione, generalità ed esempi. Grafi semplici, multigrafi, pseudografi. Il sostegno di un grafo.
La somma dei gradi è uguale al doppio del numero dei lati; conseguenze.
Matrice di adiacenza di un grafo semplice. Numero di passeggiate (“walk”) tra due vertici
e potenze della matrice di adiacenza. Isomorfismi tra grafi. Cenni sugli automorfismi di un grafo.
Grafi connessi. Alberi. Albero generatore di peso minimo. Foreste. Teorema di Cayley
(che esprime il numero degli alberi distinti con un assegnato insieme di vertici).
Grafi bipartiti e loro caratterizzazione mediante la parità della lunghezza dei cicli.
Teorema di Berge sugli accoppiamenti con massimo numero di lati (senza dimostrazione).
Teorema di accoppiamento di Philip Hall.
Grafi euleriani. Loro caratterizzazione e principali proprietà.
Grafi hamiltoniani. Teorema di Ore e suoi corollari. Chiusura di un grafo. Grafi 2-connessi.
Teorema di Bose-Manvel sui Theta-grafi.
Grafi piani. La formula di Eulero, e altre proprietà dei grafi piani.
Maggiorazione del numero dei lati di un grafo piano in funzione del calibro e del numero dei vertici.
Grafi dei poliedri. Applicazioni ai poliedri regolari.
Non planarità del grafo di Petersen. Il teorema di Kuratowski (senza dimostrazione).
Teorema di Grinberg sui grafi piani hamiltoniani.
Colorazione di carte geografiche. Mappe 2-colorabili. Il teorema dei quattro colori (senza dimostrazione).
Il grafo duale. Colorazione dei vertici di un grafo. Il teorema dei cinque colori. Numero cromatico.
Il teorema di Brooks (senza dimostrazione).
Colorazione dei lati di un grafo. Indice cromatico. Teorema di Koenig sull’indice cromatico di un grafo bipartito. Teorema di Vizing (senza dimostrazione).
Colorazione dei lati di un grafo completo, e applicazioni.
Teorema di Turan. Teorema di Ramsey.
Questa parte del programma corrisponde ai capitoli 1, 2, 3 e 4 degli appunti
di Teoria dei Grafi (vers. 1.0 o successiva) redatti dal prof. Carlo Casolo
(omettendo le sezioni 2.4 e 3.3, la dimostrazione dei teoremi 3.9, 3.10 e 4.2, la proposizione 4.8 e i teoremi 4.9
e 4.10) opportunamente integrati dagli appunti su Alberi e Grafi Piani
(vers. 0.1 o successiva) e da altri appunti (redatti dal docente e dal dott. Virgilio Pannone)
consegnati brevi manu agli studenti.