Algorytm Borůvki: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
poprawa linków, lit. |
imiona odkrywców i linki |
||
Linia 3:
'''Algorytm Borůvki''' wyznacza [[minimalne drzewo rozpinające]] dla grafu nieskierowanego ważonego, o ile jest on spójny. Innymi słowy, znajduje drzewo zawierające wszystkie wierzchołki grafu, którego waga jest najmniejsza możliwa. Jest to przykład [[algorytm zachłanny|algorytmu zachłannego]].
Pierwszy raz opublikowany został w 1926 roku przez [[Otakar Borůvka|Otakara Borůvkę]] jako metoda efektywnej konstrukcji sieci energetycznych. Algorytm ten został potem ponownie wymyślony przez [[Gustave Choquet|Choqueta]] w 1938, potem przez [[Kazimierz Florek|Florka]], [[Jan Łukasiewicz|Łukasiewicza]], [[Julian Perkal|Perkala]], [[Hugo Steinhaus||Steinhausa]] i [[Stefan Zubrzycki|Zubrzyckiego]] w 1951 i ostatecznie przez Sollina w latach 60. Ponieważ Sollin był jedynym zachodnim informatykiem wśród wymienionych tu osób, często algorytm jest nazywany jego nazwiskiem.
== Algorytm ==
| |||