This HTML5 document contains 14 embedded RDF statements represented using HTML+Microdata notation.

The embedded RDF content will be recognized by any processor of HTML5 Microdata.

Namespace Prefixes

PrefixIRI
wikipedia-huhttp://hu.wikipedia.org/wiki/
dcthttp://purl.org/dc/terms/
dbohttp://dbpedia.org/ontology/
foafhttp://xmlns.com/foaf/0.1/
dbpedia-huhttp://hu.dbpedia.org/resource/
prop-huhttp://hu.dbpedia.org/property/
rdfshttp://www.w3.org/2000/01/rdf-schema#
rdfhttp://www.w3.org/1999/02/22-rdf-syntax-ns#
n10http://hu.dbpedia.org/resource/Sablon:
provhttp://www.w3.org/ns/prov#
xsdhhttp://www.w3.org/2001/XMLSchema#
n6http://hu.dbpedia.org/resource/Kategória:

Statements

Subject Item
dbpedia-hu:Borůvka-algoritmus
rdfs:label
Borůvka-algoritmus
dct:subject
n6:Keresőalgoritmusok n6:Gráfalgoritmusok n6:Feszítőfa
dbo:wikiPageID
1704316
dbo:wikiPageRevisionID
22656098
prop-hu:wikiPageUsesTemplate
n10:Jegyzetek n10:Fordítás n10:Math
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.
prov:wasDerivedFrom
wikipedia-hu:Borůvka-algoritmus?oldid=22656098&ns=0
dbo:wikiPageLength
8365
foaf:isPrimaryTopicOf
wikipedia-hu:Borůvka-algoritmus
Subject Item
wikipedia-hu:Borůvka-algoritmus
foaf:primaryTopic
dbpedia-hu:Borůvka-algoritmus