| dbo:abstract
|
- A Borůvka-algoritmus egy mohó algoritmus mely alkalmas egy minimális feszítőfa megkeresésére egy olyan gráfban, amelyben az összes él különbözik, vagy egy minimális feszítőerdő megtalálására olyan gráf esetén, amely nem kapcsolódik. Elsőként 1926-ban Otakar Borůvka tette közzé mint egy hatékony módszert Morvaország villamos hálózatának kiépítéséhez. Az algoritmust Choquet fedezte fel újra 1938-ban; majd Florek, Łukasiewicz, Perkal, Steinhaus és Zubrzycki 1951-ben; és újra Georges Sollin 1965-ben. Ezt az algoritmust gyakran nevezik Sollin-algoritmusnak, különösen a párhuzamos számítástechnika irodalmában. Az algoritmus először megkeresi a gráf minden csúcsához tartozó legkisebb súlyú élt, és hozzáadja ezeket az éleket az erdőhöz. Ezt egy hasonló eljárás követi, amikor megkeresi a legkisebb súlyú éleket az összes eddig épített fán összehasonlítva egy másik fával, és hozzáadja ezeket az éleket az erdőhöz. Ennek a folyamatnak minden egyes ismétlése csökkenti a fák számát a gráf minden egyes összekötött komponensén belül a korábbi érték legfeljebb felére, tehát logaritmikusan sok ismétlés után a folyamat befejeződik. Amikor ez megtörténik, a hozzáadott élek halmaza egy minimum feszítőerdőt képez. (hu)
- A Borůvka-algoritmus egy mohó algoritmus mely alkalmas egy minimális feszítőfa megkeresésére egy olyan gráfban, amelyben az összes él különbözik, vagy egy minimális feszítőerdő megtalálására olyan gráf esetén, amely nem kapcsolódik. Elsőként 1926-ban Otakar Borůvka tette közzé mint egy hatékony módszert Morvaország villamos hálózatának kiépítéséhez. Az algoritmust Choquet fedezte fel újra 1938-ban; majd Florek, Łukasiewicz, Perkal, Steinhaus és Zubrzycki 1951-ben; és újra Georges Sollin 1965-ben. Ezt az algoritmust gyakran nevezik Sollin-algoritmusnak, különösen a párhuzamos számítástechnika irodalmában. Az algoritmus először megkeresi a gráf minden csúcsához tartozó legkisebb súlyú élt, és hozzáadja ezeket az éleket az erdőhöz. Ezt egy hasonló eljárás követi, amikor megkeresi a legkisebb súlyú éleket az összes eddig épített fán összehasonlítva egy másik fával, és hozzáadja ezeket az éleket az erdőhöz. Ennek a folyamatnak minden egyes ismétlése csökkenti a fák számát a gráf minden egyes összekötött komponensén belül a korábbi érték legfeljebb felére, tehát logaritmikusan sok ismétlés után a folyamat befejeződik. Amikor ez megtörténik, a hozzáadott élek halmaza egy minimum feszítőerdőt képez. (hu)
|
