Matroidi e Algoritmo Greedy

Il primo capitolo di questa trattazione presenta nove differenti definizioni assiomatiche di matroide, che si dimostrano essere equivalenti attraverso il concetto di criptomorfismo. Nel secondo capitolo andremo a studiare le matroidi grafiche come esempio di matroidi. Col termine ‘matroide grafica’ indichiamo la struttura assunta da un grafo che si verifica soddisfare i vari sistemi assiomatici introdotti nel capitolo precedente. Un’attenzione particolare è data al Polinomio di Tutte, nato come oggetto definito per i grafi ed esteso successivamente alle matroidi. L’ultimo capitolo vede invece lo studio degli algoritmi greedy per le matroidi, con esempi quali l’Algoritmo di Kruskal e l’Algoritmo di Prim per la ricerca di alberi generatori di peso minimo di un grafo dato. Viene inoltre introdotto il concetto di greedoide con l’obiettivo di dimostrare che un algoritmo greedy risolve un problema di ottimizzazione se e solo se la struttura in analisi è proprio quella di un greedoide.