L'algoritmo Kruskal - a custruzzione di u scheletru optimu

À u principiu di u seculu XIX, u geomètiricu di Berlinu, Ghjacumu Steiner, stabilisce a cumpitenza di cumu cunnessione i trè villaggi per chì a so larga era u più corta. Doppu, hà giniralizatu stu prublema: hè necessariu di truvà un puntu in u pianu chì a distanza da ellu à l'altri punti hè più chjuve. In u XX sèculu, u travagliu annantu à questu tema cuntinua. Hè statu decisu di piglià uni pochi punti è aghjunghje micca cusì chì a distanza entre elli era u più chjaru. Questu hè tutte un casu speciale di u prublema sottu studiu.

Algoritmi greedy

L'algoritmu di Kruskal riferisce à l'algoritmi "greedy" (sò ancu chjamati algoritmi di gradiente). L'esencia di quelli - a più grande tripla à ogni passu. Ùn sò sempre l'algoritmi "greedy" dà a megliu suluzione à a so cumpagnia. Ci hè una tiuria chì mostra chì, quandu s'applicate à prublemi specifiche, aducenu una solu ottima. Questa hè a teoria di matroidi. L'algoritmu Kruskal relata a tali prublemi.

Truvà u scheletru di pesu minimu

L'algoritmu sottu cunsultatu constructisce u scheletru optimu di u grafutu. U prublema quì hè cusì. Un graficu undirected senza fronti varietichi è loops hè datu, è nantu à u so settore di fruntiere ci hè datu una funzione di pisu ch'ùn aghjunghjenu à ogni alce è un numeru - u pesu di a punta - w (e). U pesu di ogni subsettu di u settore di fruntii hè determinatu da a summa di i pesi di i so ardu. Hè obligatu di truvà u scheletru di u più pocu pisu.

Descrizzione

L'algoritmu Kruskal cumu cusì. Prima, tutti i canteri di u grafutu uriginale sò urganizzati per ordine di pesi creciente. In prima, u framework ùn cuntene nisna vina, ma includenu tutti i vertici di u grafutu. Dopu u passu prossimu di l'algoritmu, una freccia hè aghjuntu à a parte di u quadru di custruitu, chì hè un boscore spanning. Ùn hè micca sceltu arbitraria. Tutti i canteri di u grafu chì ùn anu micca di u scheletru pò esse chjamatu russu è verde. I vertici di ogni ribu rossa sò in un cumpunente di a cunnessione di u boscu chì sò custruiti, è i vertici di u verde si sò in parechji cumpunenti. Per quessa, si aghjunghje un aranciu rittimu, un cìrculu aspetta, è sì u verdu in u passu di u furmali resultanti, u componente cunnessu serà più menu unu. Cusì, ùn si pò aghjunghje micca cuddinu tutale di a custruzzione resultante, ma ogni risortru verde si pò aghjunghje per fà u boscu. È aghjunghje una ribiglia verde cù un pesu minimu. U risultatu hè u marcu di u pesu più insignante.

Implementation

Scudemu u fogghiu attuali. Hè dividita u settore di vessi di u grafutu in duminii cunnessi (i so formi sindacalisi F, è ùn intrecettate micca in parechji). I verni rosse anu tutti i verticuli in una parte. Part (x) hè una funzione chì torna u nomu di a parte à a quale appartene per ogni vèrtex x. Unite (x, y) hè un prucessu chì custruisce una nova partizioni chì cumpone l 'unione di i partischi x andy è l'altri parte. Chì sia u numeru di bordu di u grafutu. Tutti issi cuncetti sò include in l'algoritmu Kruskal. Implementation:

1. Arrange all edges of the graph from the 1st to the nth pesos ascending. (Ai, bi sò i vertici di a punta cù l'indici i).

2. Per i = 1 à n ferà.

3. X: = Parte (ai).

4. Y: = Parte (bi).

5. Se x hè micca ugguali è dopu Unite (x, y), includenu a riva cù u numiru i in F.

Correctness

Semu u scheletru di u grafutu uriginale construit l'algoritmu Kruskal, è chì S sò u so sceleton arbitrariu. Hè necessariu pruvucari chì w (T) ùn esatta micca w (S).

Seria u settore di e tune di S, P u settore di bordi di T. Si S ùn hè micca uguali a T, allura esisti un aristò è di T chì ùn ùn hè di appartene à S. Uni è à S. Formulemos un cicle, chjamemu C. Cumpigliamosi da C ogni spezione chì appartene à S. Un novu marcu serà uttenutu, perchè tutti i dui vignetti è i vertici in questu hè listessu. U so pezzu ùn sia più di w (S), postu chì w (et) hè micca più grande que w (es) da l'algoritmu Kruskal. Questa operazione (a sustituzione di e verges di S per i canteri di T) si ripetireva finu à ottene u T. U pesu di ogni schema susseglièvule ùn hè più grande ca u pesu di l'antecedente, da quale segue chì w (T) hè di più w (S).

Inoltre, a correcità di l'algoritmu di Kruskal segue da u teorema Rado-Edmonds in matroidi.

Esempii di l'applicazione di l'algoritmu Kruskal

A graficu cù vèrtici a, b, c, d, e è edges (a, b), (a, e), (b, c), (b, e), (c, d), (c, e) , (D, e). I pesi di i canteri sò ammustrati in a tavula è in a figura. In u iniziu, u furasteru custruttu F cuntene tutti i vertici di u grafutu è ùn mancu un lignu solu. L'algoritmu Kruskal prima aghjunghjera una freccia (a, e), postu chì u so pesu hè u più chjuve, è i vertici a e e sò in cumpunenti di cunnessione di i cuncettanti di u fossu F (u borde (a, e) hè verde), da u borde (c, d), perchè Chì sta cima hè u pesu minimu da i spiculi di u graficu chì ùn hè micca di a F, è hè verde, perchè per i stessi motivi un agenti (a, b) hè aghjuntu. Ma l'upertu (b, e) hè saltatu, ancu s'ellu hè u pesu u minimu di l'arnesi remissi, perchè hè russu: i vertici chì e pertenenu da u stessu componente cunnessu di u fustu F, per esse, se aghjustà una freccia (b, e) à F, Ciculu. Allora u vignetu verde (b, c) hè aghjuntu, u vignetu rossu (c, e) hè skipped, è dopu d, e. Cusì, i spiculi (a, e), (c, d), (a, b), (b, c) sò agghiunciuti successivamente. Da ellu, u scheletru optimu di u grafutu uriginale cumporta. Questu hè cumu u travagliu di l'algoritmu in stu casu Aghju tinutu. Un esempiu palesa questu.

A figura si mostra un grafu cunzistenti di duie cumpunenti cunnessi. Linde di Linnu à l'ombri di u marcu otticu (verdi), custruitu cù l'algoritmu Kruskal.

A figura supirria mostra u gràficu iniziale, è nantu à u puntu bassu - u scheletru di u pesu minimu, custruitu per questu cù l'aiutu di l'algoritma cunzidutu.

A secùncia di verni aggiudate: (1.6); (0,3), (2,6) o (2,6), (0,3) - ùn importa micca; (3.4); (0,1), (1,6) o (1,6), (0,1) hè indifferente (5,6).

L'algoritmu di Kraskal find application practical, per esempiu, per ottimisimu cummincii di cumunicazione, strade in novi microdistriti in ogni località di u paese, ancu in altri casi.