Minimaalne ulatuspuu: definitsioon, omadused ja näited
Minimaalne ulatuspuu: definitsioon, omadused ja praktilised näited graafiteooriast. Õpi algoritmid, rakendused ja samm-sammult selgitused optimaalse võrgustruktuuri leidmiseks.
Mitmeid probleeme graafiteooriast nimetatakse minimaalseks läbivaks puuks (tuntud ka kui minimaalne ulatuspuu). Graafiteoorias on puu selline alamgraaf, mis ühendab kõiki tippe nii, et iga kahe tipu vahel on täpselt üks lihtne tee. Näiteks kui graaf kujutab mitmeid linnu, mida ühendavad teed, võiks valida mitme linna vahel sellised ühendused, et igast linnast on võimalik jõuda igasse teise linna, kuid ei tekiks liigseid ringe (ühe linna paarist teise oleks täpselt üks tee).
Mis on minimaalne ulatuspuu?
Kui graafi servadele on määratud kaalud (näiteks teekilomeetrid, maksumus või läbitav aeg), siis on huvipakkuv selline läbiv puu, mille servade kaalude summa on võimalikult väike. Seda alamgraafi nimetatakse minimaalseks ulatuspuuks (MST). Oluline on mõista:
- MST on alati puu: ühendav ja tsüklitevaba.
- MST sisaldab täpselt V−1 serva, kus V on tippe (sest iga puul on V−1 serva).
- Kui algne graaf on lahus ja ei ühenda kõiki tippe, siis minimaalset ulatuspuud ei eksisteeri kogu graafi jaoks — sel juhul räägitakse minimaalsest ulatusmetspuust (minimum spanning forest), mis koosneb iga komponendi MST-st.
Peamised omadused
- Lõikude (cut) omadus: Iga lõikude (tipu jaotus) puhul, mis jagab graafi kaheks osaks, kuulub mõnele MST-le lõigus väikseima kaaluga serv. See omadus aitab algoritmides valida sobivaid servi.
- Tsükli omadus: Kui vaadata suvalist tsüklit graafis, siis suurima kaaluga serv sellele tsüklile ei kuulu ühegi MST-sse (võib-olla mitme serva sama maksimaalse kaaluga puhul on alternatiive).
- Unikaalsus: Kui kõik servade kaalud on erinevad, siis on MST ainulaadne. Kui on võrdsete kaaludega servi, võib olla rohkem kui üks erinev MST.
- Optimaalsus: MST minimeerib kõigi võimalike läbivate puude servade kaalude summat.
Näited
Lihtne näide: nelja tipu A, B, C, D korral, kus servade kaalud on järgmised — AB:1, AC:3, AD:4, BC:2, BD:5, CD:6. Üks minimaalne ulatuspuu sisaldab servi AB (1), BC (2) ja AC või AD vastavalt pisut erinevale kaalule; siin sobib AB+BC+AD kokku 1+2+4=7 ning see on väikseim võimalik summa, mis ühendab kõiki tippe ilma tsükliteta.
Konkreetsemalt linna- ja teedepildi puhul valib MST need teed, mille kogupikkus (või maksumus) on väikseim, kuid mis siiski tagavad ühenduse kõigi linnade vahel.
Levinumad algoritmid
- Kruskal’i algoritm: Sorteeritakse kõik servad kaalude järgi ja lisatakse järk-järgult väiksekaalulisi servi, vältides tsükleid (üldjuhul kasutatakse selleks hulgaliseltühenduse/union-find andmestruktuuri). Ajakompleksus peamiselt O(E log E) servade sorteerimise tõttu.
- Prim’i algoritm: Alustatakse ühelt tipult ja laiendatakse puu samm-sammult, iga sammu juures lisades väiksekaalulise servi, mis ühendab juba valitud tipud ülejäänud graafi tipuga. Hea prioriteedijärjekorraga (min-heap) saab keerukuseks O(E + V log V) või O(E log V) sõltuvalt implmentatsioonist.
- Borůvka algoritm: Paralleelne meetod, mis mitmes etapis liidab komponente, iga etapis valides igast komponendist väikseimad väljuvad servad. Kasulik paralleelseks või jaotatud arvutuseks.
Rakendused
- Võrgukujundus: optimaalse võrguühenduse planeerimine (elektrivõrgud, torustikud, sidevõrgud).
- Transport ja logistika: tee- või raudteevõrkude planeerimine minimaalse kuluga.
- Andmeside ja arvutivõrgud: võrguskeemide, kaablite või optika paigutuse optimeerimine.
- Piltide modelleerimine ja klasterdamine: MST abil leitakse andmepunktide vahelisi struktuure ja lähedasi ühendusi.
Märkus ja kokkuvõte
Minimaalne ulatuspuu on fundamentaalne mõiste graafiteoorias ja optimeerimises. Kuigi graafist võib olla rohkem kui üks läbiv puu, aitab kaalude lisamine leida nende seas optimaalse (minimaalse kaaluga) lahenduse. Kui kõik servad on sama kaaluga, on iga puu minimaalseks; kui kõik kaalud on erinevad, siis MST on ainulaadne.
Tasandilise graafi minimaalne sirutuspuu. Iga serv on tähistatud oma kaaluga, mis on siinkohal ligikaudu proportsionaalne selle pikkusega.
Minimaalse ulatusliku puu leidmine
Esimene katse
Võib olla väga lihtne teha algoritm, mis avastab minimaalse ulatusliku puu:
funktsioon MST(G,W): T = {} kuni T ei moodusta sirguspuud: leida minimaalne kaalutud serv E-s, mis on T jaoks ohutu T = T union {(u,v)} return TSellisel juhul tähendab "ohutu", et serva kaasamine ei moodusta graafis tsüklit. Tsükkel tähendab, et alustatakse ühest tipust, liigutakse mitmesse teise tippu ja jõutakse uuesti alguspunkti, ilma et kasutataks sama serva kaks korda.
Ajalugu
Tšehhi teadlane Otakar Borůvka töötas 1926. aastal välja esimese teadaoleva algoritmi minimaalse ulatusliku puu leidmiseks. Ta soovis lahendada probleemi, kuidas leida Moraavia tõhusat katvust elektriga. Tänapäeval on see algoritm tuntud kui Borůvka algoritm. Tänapäeval kasutatakse tavaliselt veel kahte algoritmi. Ühe neist töötas 1930. aastal välja Vojtěch Jarník ja rakendas praktikas Robert Clay Prim 1957. aastal. Edsger Wybe Dijkstra avastas selle uuesti 1959. aastal ja nimetas seda Primi algoritmiks. Teist algoritmi nimetatakse Kruskali algoritmiks ja selle pulbitses Joseph Kruskal 1956. aastal. Kõik kolm algoritmi on ahned ja töötavad polünoomiaja jooksul.
Seni kõige kiirema minimaalse hajutuspuu algoritmi töötas välja Bernard Chazelle. Algoritm põhineb pehmel kuhilal, mis on ligikaudne prioriteetide järjekord. Selle tööaeg on O(m α(m,n)), kus m on servade arv, n on tippude arv ja α on Ackermanni funktsiooni klassikaline funktsionaalne pöördväärtus. Funktsioon α kasvab äärmiselt aeglaselt, nii et praktilistel eesmärkidel võib seda pidada konstantiks, mis ei ole suurem kui 4; seega võtab Chazelle'i algoritm väga lähedaselt lineaarset aega.
Milline on kõige kiirem võimalik algoritm selle probleemi lahendamiseks? See on üks vanimaid lahtisi küsimusi arvutiteaduses. Ilmselgelt on olemas lineaarne alumine piir, sest me peame vähemalt uurima kõiki kaalusid. Kui servade kaalud on täisarvud, mille bitide pikkus on piiratud, siis on teada deterministlikud algoritmid, mille tööaeg on lineaarne. Üldiste kaalude puhul on olemas randomiseeritud algoritmid, mille eeldatav jooksuaeg on lineaarne.
Probleemile võib läheneda ka hajutatult. Kui iga sõlme käsitatakse arvutina ja ükski sõlm ei tea midagi peale oma ühendatud linkide, saab ikkagi arvutada jaotatud minimaalse võrkpuu.
Küsimused ja vastused
Küsimus: Mis on minimaalne sirutuspuu graafiteoorias?
V: Minimaalne läbiv puu on graafiteoorias puu, mis minimeerib servadele omistatud kogukaalusid.
K: Mis on puu graafiteoorias?
V: Graafiteoorias on puu kõigi tippude ühendamine nii, et mis tahes tipust on ainult üks tee puu mis tahes teise tippu.
K: Mis on teede valimise eesmärk graafiteooria stsenaariumis, mis kujutab linnu?
V: Teede valimise eesmärk linnu kujutavas graafiteooria stsenaariumis on võimaldada igasse linna jõuda igast teisest linnast, kuid mitte rohkem kui üks võimalik tee ühest linnast teise.
K: Kas graafil võib olla rohkem kui üks läbiv puu?
V: Jah, graafil võib olla rohkem kui üks läbiv puu.
K: Mis vahe on minimaalsel läbival puul ja teistel graafiteooria puudel?
V: Minimaalne läbiv puu minimeerib servade kogukaalud, samas kui teistel puudel seda omadust ei ole.
K: Mis on servad graafiteoorias?
V: Servad on graafiteoorias kahe tipu vahelised ühendused.
K: Kas graafis võib olla rohkem kui üks minimaalne läbiv puu, mille servad on erineva kaaluga?
V: Jah, sõltuvalt sellest, milline on graafi välimus, võib olla rohkem kui üks minimaalne läbiv puu.
Otsige