Riassunto analitico
L’obiettivo della tesi è lo studio dettagliato di problemi riguardanti flussi e “matchings” in grafi di vario genere.
Prima di tutto ho studiato problemi di flusso in reti “networks”, da definizioni e nozioni base fino ad uno dei risultati più importanti: il teorema di Ford-Fulkerson. Successivamente ho studiato problemi di “matchings”, dando particolare attenzione ai problemi d’accoppiamento in grafi bipartiti. Ho sempre cercato di evidenziare come un problema di flusso possa essere visto come un problema d’accoppiamento, mostrando le equivalenze che intercorrono fra i principali teoremi di queste due classi di problemi. Un capitolo è dedicato, invece, a due importanti algoritmi per la risoluzione di questi due problemi, entrambi basati sullo stesso principio, i cammini incrementali.
L’ultimo capitolo riguarda invece i flussi a valore in gruppi abeliani finiti, particolare rilevanza viene data ai flussi a valore mai zero, mostrando risultati recenti in direzione di tre teoremi congetturati da Tutte sull’argomento.
|
Abstract
Objective of this thesis is to study in detail problems regarding flows and matchings in graphs of various kinds.
First I studied flows in networks, from very basic definitions to one of the most important result: the Ford-Fulkerson Theorem. Next I analyzed matchings, giving particular attention to matching problems in bipartite graphs. I always tried to enlighten how a flow problem can be seen as a matching problem and viceversa, showing equivalences between the major theorems of these two classes of problems. One chapter is dedicated to show two important algorithms to solve these two kind of problems, both of them are based on the same principle, augmenting paths.
The last chapter involves finite abelian group valued flows, focusing on nowhere zero flows and recent results towards three Tutte’s conjectures.
|
