Appunti di Interfacoltà - Università degli Studi del Molise

La Teoria dei Grafi ha svariate applicazioni, sia nel campo della matematica pura che di quella applicata. Il presente testo non si prefigge il ruolo di essere utilizzato come un manuale didattico completo, ma piuttosto vuole presentare, attraverso degli esempi, l’importanza di questa branca nel contesto scientifico. Dopo due capitoli introduttivi, volti a spiegare cosa sia un grafo e quali siano le sue principali caratteristiche, l’autore passa a fornire un primo esempio di applicazioni degli stessi attraverso lo studio del problema delle colorazioni delle mappe, introducendo il concetto di cammino e isomorfismo tra grafi. Nel capitolo successivo si passano ad analizzare le caratteristiche e le applicazioni dei grafi orientati, per poi disquisire sui legami che tali grafi hanno con la combinatoria. I successivi capitoli del testo concentrano l’attenzione sull’analisi e sull’utilizzo dei grafi come strumento di mappatura e ricerca: dopo aver introdotto alcuni algoritmi fondamentali, quali quello di sorting, si passa all’analisi della K-fattorizzazione di un grafo e ad altri algoritmi fondamentali per lo studio dei cosiddetti “Grafi Euleriani”. Il manuale si chiude con l’analisi di altri importanti algoritmi di fattorizzazione e il loro utilizzo per lo studio di esempi concreti, quali ad esempio il problema dei ponti di Konigsberg.