Determinante nei grafi: aspetti combinatori

In questa tesi si studia il legame tra il determinante di una matrice e la struttura di un grafo ad essa associato. Nel primo capitolo si analizza la matrice di Tutte e si mostra come il suo determinante permetta di caratterizzare algebricamente l’esistenza di perfect matching in un grafo, fornendo così la formulazione algebrica del teorema di Tutte. Nel secondo capitolo si introduce il metodo di valutazione grafica del determinante di Drucker e Goldschmidt, che esprime il determinante con una formula ricorsiva indicizzata sui cicli di un grafo orientato e pesato associato alla matrice. Il metodo viene applicato alle matrici sparse e successivamente utilizzato per reinterpretare i meccanismi combinatori già descritti nel primo capitolo, che sono alla base del teorema di Tutte. Dalla tesi emerge quindi come i tre livelli: grafo, permutazioni e sviluppo del determinante, interpretino gli stessi meccanismi combinatori.