Matroidi e Algoritmo Greedy

Dore, Lucia (2020) Matroidi e Algoritmo Greedy. [Laurea magistrale], Università di Bologna, Corso di Studio in Matematica [LM-DM270]
Documenti full-text disponibili:
[img] Documento PDF (Thesis)
Disponibile con Licenza: Creative Commons: Attribuzione - Non commerciale - Condividi allo stesso modo 4.0 (CC BY-NC-SA 4.0)

Download (796kB)

Abstract

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.

Abstract
Tipologia del documento
Tesi di laurea (Laurea magistrale)
Autore della tesi
Dore, Lucia
Relatore della tesi
Scuola
Corso di studio
Indirizzo
Curriculum C: Didattico
Ordinamento Cds
DM270
Parole chiave
matroide greedoide grafo algoritmo greedy polinomio tutte Prim Kruskal
Data di discussione della Tesi
26 Giugno 2020
URI

Altri metadati

Statistica sui download

Gestione del documento: Visualizza il documento

^