L'Algoritmo di Wilson: Alberi Ricoprenti Uniformi, Passeggiate Aleatorie e la Funzione di Green

La tesi esplora l'algoritmo di Wilson, un metodo per la generazione di Alberi Ricoprenti Uniformi (UST)L'algoritmo si basa sulla teoria delle passeggiate aleatorie, utilizzando il concetto di passeggiata aleatoria con cancellazione di cicli (Loop-Erased Random Walk, LERW). Il percorso della tesi si articola in tre capitoli. Il primo capitolo introduce i prerequisiti matematici essenziali, tra cui la teoria dei grafi, le passeggiate aleatorie e, in particolare, l'apparato analitico costituito dall'operatore Laplaciano discreto e dalla sua inversa, la funzione di Green. Nel secondo capitolo, è la dimostrazione analitica del teorema di Wilson. Sfruttando le proprietà della funzione di Green, si dimostra rigorosamente che l'algoritmo genera ogni albero ricoprente con probabilità uniforme, svelando un'intima dualità tra probabilità, analisi su grafi e combinatoria. Viene inoltre discussa la proprietà di indipendenza dall'ordine di scelta dei vertici. Il terzo capitolo sposta l'attenzione dalla teoria alla pratica, presentando l'implementazione computazionale dell'algoritmo e una serie di simulazioni significative. Vengono visualizzati gli alberi generati su diverse tipologie di grafi e viene fornita una verifica empirica dell'uniformità della distribuzione tramite un'analisi statistica su un grafo di piccole dimensioni. Complessivamente, la tesi offre una disamina completa dell'algoritmo di Wilson.