Albero ricoprente minimo
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.
L'albero minimo di un grafico planare. Ogni bordo è etichettato con il suo peso, che qui è approssimativamente proporzionale alla sua lunghezza.
Trovare l'albero minimo di campata
Un primo tentativo
Può essere molto semplice realizzare un algoritmo che scopra un albero di minima ampiezza:
funzione MST(G,W) : T = { } mentre T non forma un albero di spaziatura: trovare il bordo minimo ponderato in E che è sicuro per T T T = T unione {(u,v) } ritorno TIn questo caso, "sicuro" significa che l'inclusione del bordo non costituisce un ciclo nel grafico. Un ciclo significa partire da un vertice, viaggiare verso un certo numero di altri vertici e finire di nuovo al punto di partenza senza utilizzare lo stesso spigolo due volte.
Storia
Lo scienziato ceco Otakar Borůvka ha sviluppato il primo algoritmo conosciuto per la ricerca di un albero di minima estensione, nel 1926. Voleva risolvere il problema di trovare una copertura efficiente della Moravia con l'elettricità. Oggi questo algoritmo è conosciuto come l'algoritmo di Borůvka. Altri due algoritmi sono comunemente usati oggi. Uno di questi è stato sviluppato da Vojtěch Jarník nel 1930 e messo in pratica da Robert Clay Prim nel 1957. Edsger Wybe Dijkstra lo riscoprì nel 1959 e lo chiamò algoritmo di Prim. L'altro algoritmo si chiama algoritmo di Kruskal, ed è stato realizzato da Joseph Kruskal nel 1956. Tutti e tre gli algoritmi sono avidi, e funzionano in tempo polinomiale.
L'algoritmo dell'albero di spaziatura minima più veloce fino ad oggi è stato sviluppato da Bernard Chazelle. L'algoritmo si basa sul mucchio morbido, una coda di priorità approssimativa. Il suo tempo di esecuzione è O(m α(m,n)), dove m è il numero dei bordi, n è il numero dei vertici e α è il classico inverso funzionale della funzione Ackermann. La funzione α cresce estremamente lentamente, cosicché a tutti gli effetti pratici può essere considerata una costante non superiore a 4; così l'algoritmo di Chazelle prende un tempo molto vicino a quello lineare.
Qual è l'algoritmo più veloce possibile per questo problema? Questa è una delle domande aperte più antiche dell'informatica. C'è chiaramente un limite inferiore lineare, poiché dobbiamo almeno esaminare tutti i pesi. Se i pesi del bordo sono interi con una lunghezza di bit delimitata, allora gli algoritmi deterministici sono noti con un tempo di esecuzione lineare. Per i pesi generali, esistono algoritmi randomizzati il cui tempo di esecuzione previsto è lineare.
Il problema può essere affrontato anche in modo distribuito. Se ogni nodo è considerato un computer e nessun nodo conosce nulla se non i propri collegamenti collegati, si può comunque calcolare l'albero di spaziatura minima distribuita.
Domande e risposte
D: Che cos'è un albero a scansione minima nella teoria dei grafi?
R: Nella teoria dei grafi, un minimum spanning tree è un albero che minimizza i pesi totali legati ai bordi.
D: Che cos'è un albero nella teoria dei grafi?
R: Un albero è un modo per collegare tutti i vertici tra loro nella teoria dei grafi, in modo che ci sia un solo percorso da un vertice a qualsiasi altro vertice dell'albero.
D: Qual è lo scopo della selezione delle strade in uno scenario di teoria dei grafi che rappresenta le città?
R: Lo scopo della selezione delle strade in uno scenario di teoria dei grafi che rappresenta le città è quello di consentire a ogni città di essere raggiunta da ogni altra città, ma con non più di un percorso possibile per viaggiare da una città all'altra.
D: Un grafo può avere più di uno spanning tree?
R: Sì, un grafo può avere più di uno spanning tree.
D: Qual è la differenza tra un minimum spanning tree e altri alberi nella teoria dei grafi?
R: Un albero a campata minima minimizza i pesi totali legati ai bordi, mentre gli altri alberi non hanno questa caratteristica.
D: Cosa sono i bordi nella teoria dei grafi?
R: I bordi sono le connessioni tra due vertici nella teoria dei grafi.
D: Ci può essere più di un albero minimo in un grafo con bordi ponderati diversi?
R: Sì, a seconda dell'aspetto del grafo, può esistere più di un albero minimo.
