Prerequisites:
The course requires a minimal acquaintance with combinatorics and discrete mathematics and the proof techniques used therein, primarily, mathematical induction. All other necessary background will be covered in the course itself.
Description:
Graph theory has proven to be a rich and elegant field of discrete mathematics. In recent years, graph theory has also yielded numerous applications in discrete mathematics and theoretical computer science. The course covers the classic results and subtopics in the field as well as providing an introduction to current areas of research.
The general topics covered in the course are:
Basic Concepts: trees, paths cycles and connectivity. Hamiltonian cycles and sufficient conditions for their existence. Eulerian walks and the characterization of Eulerian graphs. Subgraphs, contraction and deletion of edges, graph minors. Graph connectivity and Menger's theorem. Max flow/min cut in graphs.
Graph Structures: Matchings in bipartite graphs (König and Hall's Theorems). Tutte's theorem for matchings in general graphs. Dilworth's theorem. Planar graphs. Kuratowski's theorem, planar duality. Extremal graph theory, Turan's theorem for complete subgraphs. Introduction to Ramsey theory and the existence of Ramsey numbers.
Graph Decomposition: Block decomposition of graphs. Ear decomposition of 2-connected graphs. Characterization of 3-connected graphs.
Graph Properties: Graph coloring. 5-color theorem. Edge coloring. Brook and Vizing's theorems.
Recommended texts:
Prerequisiti:
Si richiede una minima conoscenza di combinatorica e probabilità discreta. In generale, il background necessario allo studio del corso sarà offerto nel corso stesso.
Descrizione:
La Teoria dei Grafi é un campo della Combinatoria con numerose applicazioni sia alla matematica che all'informatica. Si tratta di un'area di ricerca recente che, a parte pochi risultati classici, si é sviluppata negli ultimi decenni e molte sono ancora le domande alle quali bisogna rispondere. I risultati sono spesso intuitivi e le dimostrazioni sono eleganti e basate su ragionamenti di tipo visivo e deduttivo. Ciò si traduce in algoritmi pratici e efficienti. Questo corso offre una introduzione generale all'area e ai concetti e alle idee della ricerca attuale.
Gli argomenti trattati riguardano le categorie seguenti:
Concetti di base: alberi, cammini, cicli e connetività; algortimo di Kruskal; cicli Hamiltoniani e condizioni sufficienti per la loro esistenza; cicli Euleriani e caratterizzazione dei grafi Euleriani; sottigrafi, contrazioni e eliminazioni di lati, minori di grafi. Connetività generale e Teorema di Menger; Max/flow min cut e algoritmi.
Strutture in grafi: Matchings in grafi bipartiti (Teorema di König e Hall), Teorema di Tutte per matchings in grafi generici; Teorema di Dilworth. Grafi planari: teorema di Kuratowski, dualità planare. Teoria dei grafi estrema, Teorema di Turan su sottografi completi. Introduzione alla teorai di Ramsey ed esistenza dei numeri di Ramsey.
Decomposizione di grafi: decomposizione a blocchi di grafi, la decomposizione "ear" di grafi 2-connessi e caratterizzazione di grafi 3-connessi.
Proprietà dei grafi: Colorazione di grafi, Teorema dei 5 colori, colorazione dei lati, Teorema di Brook e Teorema di Vizing.
Testi:
Conoscenze acquisite:
Familiarità con le tecniche e i risultati della Teoria dei Grafi classica e consapevolezza delle maggiori aree di ricerca.
Competenze acquisite:
Abilità nello scrivere e organizzare dimostrazioni matematiche per la risoluzione di problemi di Teoria dei Grafi.
Abilità di estrazione di algoritmi di grafi da dimostrazioni deduttive.
Capacità di studio di argomenti avanzati di ricerca nella teoria dei grafi.