Kruskalo minimalusis jungiamasis medis
Nagrinėkite briaunas nemažėjančia svorių tvarka: pridėkite briauną tada ir tik tada, kai jos galinės viršūnės priklauso skirtingoms esamoms jungumo komponentėms, o tada tas komponentes sujunkite.
Esminės žinios
Nagrinėkite briaunas nemažėjančia svorių tvarka: pridėkite briauną tada ir tik tada, kai jos galinės viršūnės priklauso skirtingoms esamoms jungumo komponentėms, o tada tas komponentes sujunkite. Pjūvio savybė įrodo, kad gautas medis yra mažiausio svorio; nejungiesiems grafams šis metodas duoda minimalųjį jungiamąjį mišką.
Sąlygos ir taikymo ribos
- Grafas yra baigtinis, neorientuotasis ir svorinis.
- Kai operacijoms su komponentėmis naudojama efektyvi nesikertančių aibių duomenų struktūra, bendrąjį sudėtingumą lemia O(E log E) rūšiavimas.
Šaltiniai · 1
Šaltiniai
Šaltiniai išlaiko savo taikymo ribas. Vien nuoroda nepatvirtina kiekvieno teiginio patikrinimo.
Pagrindimas ir peržiūra
Paskaita 3: Kruskalo algoritmas ir įrodymas, grindžiamas miško invariantu bei pjūviu.
2026-10-10 · Nepriklausoma DI redakcinė peržiūra: perskaityti visi 241 glaustas teiginys, hipotezės, atskirai pateiktos lygtys ir susitarimai bei visos 596 kilmės semantinės nuorodos; peržiūrėta visa autoriaus 241 įrašo tikslių šaltinių patikros matrica ir nurodyti apribojimai. Siekiant aprėpti visą rinkinį, perskaityti 105 ankstesni faktiniai paveldėti matematikos ir informacijos įrašai. Tikslinės nepriklausomai peržiūrėtos pirminių šaltinių dalys išvardytos toliau; tuo NETEIGIAMA, kad kiekvieno cituojamo šaltinio visas tekstas ar kiekvienas įrodymas buvo nepriklausomai perskaitytas iš naujo. Tai DI atliekama informacinio turinio peržiūra, o ne žmogaus atliekamas dalykinis sertifikavimas, išsamus vadovėlio atkūrimas ar eksperimentinis atkartojimas. Patvirtinimas: mathematics-information-independent-content-review.1.
Įrašo informacija
Nuolatinė nuoroda į šį įrašą ↗- Įrašo identifikatorius
- info-kruskal-spanning-tree
- Versija
- university-core.1
- Struktūruotas žinyno įrašas
- Universitetinių pagrindų plėtra