Una serie di problemi della teoria dei grafici sono chiamati Albero di spaziatura minima. Nella teoria dei grafici, un albero è un modo per collegare tutti i vertici insieme, in modo che ci sia esattamente un percorso da un qualsiasi vertice, a qualsiasi altro vertice dell'albero. Se il grafico rappresenta un certo numero di città collegate da strade, si potrebbe selezionare un certo numero di strade, in modo che ogni città possa essere raggiunta da ogni altra, ma che non ci sia più di un modo di viaggiare da una città all'altra.
Un grafico può avere più di un albero trasversale, così come possono esserci più di un modo per selezionare le strade tra le città.
Nella maggior parte dei casi, i grafici sono ponderati; ogni collegamento tra due città ha un peso: può costare qualcosa viaggiare su una data strada, o un collegamento può essere più lungo dell'altro, questo significa che ci vuole più tempo per viaggiare su quel collegamento. Nel linguaggio della teoria dei grafici, le connessioni sono chiamate bordi.
Un albero di minima estensione è un albero. Si differenzia dagli altri alberi in quanto riduce al minimo il totale dei pesi attaccati ai bordi. A seconda di come appare il grafico, ci può essere più di un albero con un'estensione minima. In un grafico in cui tutti i bordi hanno lo stesso peso, ogni albero è un albero di minima campata. Se tutti i bordi hanno pesi diversi (cioè: non ci sono due bordi con lo stesso peso), c'è esattamente un albero di minima estensione.
