L'algoritmo di Kruskal: la costruzione dello scheletro ottimale

All'inizio del XIX secolo, il geometra di Berlino, Jacob Steinerimpostare il compito di come collegare i tre villaggi in modo che la loro lunghezza fosse la più breve. Successivamente, ha generalizzato questo problema: è necessario trovare un punto sul piano in modo tale che la distanza da esso a n altri punti sia la più piccola. Nel 20 ° secolo, il lavoro su questo argomento è continuato. Si è deciso di prendere diversi punti e collegarli in modo tale che la distanza tra loro fosse la più breve. Questo è tutto un caso speciale del problema in esame.

Algoritmi avidi

L'algoritmo di Kruskal si riferisce ad algoritmi "avidi"(sono anche chiamati gradiente). L'essenza di quelli - la più grande vittoria ad ogni passo. Non sempre gli algoritmi "avidi" offrono la soluzione migliore per il compito. C'è una teoria che mostra che quando vengono applicati a problemi specifici, forniscono la soluzione ottimale. Questa è la teoria dei matroidi. L'algoritmo di Kruskal si riferisce a tali problemi.

Trovare lo scheletro del peso minimo

L'algoritmo in esame crea un ottimolo scheletro del grafico. Il problema è il seguente. Viene dato un grafo non orientato senza più spigoli e spigoli e sul suo set di bordi viene assegnata una funzione di peso w che assegna a ciascun bordo e un numero - il peso del bordo - w (e). Il peso di ciascun sottoinsieme del gruppo di spigoli è determinato dalla somma dei pesi dei suoi bordi. È necessario trovare lo scheletro del peso più piccolo.

descrizione

L'algoritmo di Kruskal funziona così. Innanzitutto, tutti i bordi del grafico originale sono disposti in ordine crescente di pesi. Inizialmente, il framework non contiene alcun bordo, ma include tutti i vertici del grafico. Dopo il passo successivo dell'algoritmo, un lato viene aggiunto alla parte già costruita del framework, che è una foresta spanning. Non è scelto arbitrariamente. Tutti i bordi del grafico che non appartengono allo scheletro possono essere chiamati rosso e verde. I vertici di ciascuna costola rossa si trovano in un componente della connessione della foresta in costruzione e i vertici del verde sono in componenti diversi. Pertanto, se si aggiunge un bordo rosso, viene visualizzato un ciclo e, se quello verde, nel passaggio foresta risultante, il componente di connettività sarà inferiore di uno. Pertanto, non è possibile aggiungere alcun bordo rosso alla costruzione risultante, ma è possibile aggiungere qualsiasi bordo verde per ottenere la foresta. E viene aggiunta una costola verde con un peso minimo. Di conseguenza, si ottiene lo scheletro del peso più piccolo.

implementazione

Denota la foresta attuale F. Divide l'insieme di vertici del grafico in domini connessi (le loro forme di unione F, e non si intersecano a coppie). I bordi rossi hanno entrambi i vertici in una parte. Part (x) è una funzione che restituisce il nome della parte a cui x appartiene per ciascun vertice x. Unite (x, y) è una procedura che costruisce una nuova partizione costituita dall'unione delle parti xey e di tutte le altre parti. Sia n il numero di bordi del grafico. Tutti questi concetti sono inclusi nell'algoritmo di Kruskal. implementazione:

1. Disporre tutti i bordi del grafico dal 1 ° all'ennesimo peso crescente. (ai, bi sono i vertici del bordo con indice i).

2. per i = 1 a n fare.

3. x: = Parte (ai).

4. y: = Parte (bi).

5. Se x non è uguale a y quindi Unite (x, y), includere il bordo con il numero i in F.

correttezza

Sia T lo scheletro del grafico originale costruito usando l'algoritmo di Kruskal, e sia S il suo scheletro arbitrario. Dobbiamo dimostrare che w (T) non supera w (S).

Sia M l'insieme dei bordi di S, P l'insieme dei bordiT. Se S non è uguale a T, allora c'è uno spigolo et dello scheletro T che non appartiene a S. Ci uniamo a et a S. Formiamo un ciclo, lo chiamiamo C. Togliamo da C qualsiasi spigolo che appartiene a S. Si ottiene un nuovo scheletro, e ci sono tanti vertici in esso. Il suo peso non supera w (S), poiché w (et) non è maggiore di w (es) dall'algoritmo di Kruskal. Questa operazione (la sostituzione dei bordi di S con i bordi di T) sarà ripetuta fino a ottenere T. Il peso di ogni successivo scheletro risultante non è maggiore del peso del precedente, da cui segue che w (T) è al massimo w (S).

Inoltre, la correttezza dell'algoritmo di Kruskal deriva dal teorema di Rado-Edmonds sui matroidi.

Esempi dell'applicazione dell'applicazione dell'algoritmo di Kruskal

Dato un grafico con vertici a, b, c, d, e e bordi (a,b), (a, e), (b, c), (b, e), (c, d), (c, e), (d, e). I pesi dei bordi sono riportati nella tabella e nella figura. Inizialmente, costruzione foresta F contiene tutti i vertici del grafo e non contiene costole. Algoritmo di Kruskal aggiungere prima costola (a, e), dal momento che il peso ha avuto il più basso, ed i vertici A e E sono in diversi componenti di connettività del legno F (costola (a, e) è verde), poi la costola (c, d), perché che almeno questo peso bordo dei bordi del grafico, non appartenendo a F, ed è verde, poi per le stesse ragioni maturano bordo (a, b). Ma è passato il bordo (b, e), anche se lui e il peso minimo dei bordi rimanenti, perché è rosso: i b ed e vertici appartengono alla stessa componente di connettività foresta F, vale a dire, se a questo aggiungiamo F bordo (b, e), è formato ciclo. Poi aggiunto bordo verde (b, c) bordo rosso, viene passato (c, e), e poi d, e. sequenzialmente Così, vengono aggiunti bordi (a, e), (c, d), (a, b), (b, c). Da nihera telaio ottimale ed è costituito dal grafico originale. Quindi, in questo caso si opera un algoritmo Ho tinto. Un esempio mostra questo.

La figura mostra un grafico costituito da due componenti di connettività. Le linee in grassetto mostrano i bordi della struttura ottimale (verde), costruita utilizzando l'algoritmo di Kruskal.

La figura in alto mostra il grafico originale e in quello inferiore lo scheletro del peso minimo, costruito per esso con l'aiuto dell'algoritmo considerato.

La sequenza dei bordi aggiunti: (1.6); (0,3), (2,6) o (2,6), (0,3) - non importa; (3,4); (0,1), (1,6) o (1,6), (0,1), è anche indifferente (5,6).

L'algoritmo di Kruskal trova applicazione pratica, ad esempio, per ottimizzare i blocchi di comunicazione, le strade nei nuovi quartieri nelle località di ciascun paese e anche in altri casi.