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.

Graph Theory da Reinhard Diestel