Minimaalne laienemispuu

Mitmeid probleeme graafiteooriast nimetatakse minimaalseks läbivaks puuks. Graafiteoorias on puu viis, kuidas ühendada kõik tipud omavahel nii, et ükskõik millisest tipust on täpselt üks tee ükskõik millise teise tipu juurde. Kui graaf kujutab mitmeid linnu, mida ühendavad teed, võiks valida mitu teed nii, et igast linnast oleks võimalik jõuda igasse teise linna, kuid ühest linnast teise ei oleks võimalik sõita rohkem kui ühe tee kaudu.

Graafil võib olla rohkem kui üks läbiv puu, nagu ka linnade vaheliste teede valimiseks võib olla rohkem kui üks viis.

Enamasti on graafikud kaalutud; igal kahe linna vahelisel ühendusel on kaal: antud teel sõitmine võib maksta midagi või üks ühendus võib olla pikem kui teine, mis tähendab, et selle ühenduse läbimiseks kulub rohkem aega. Graafiteooria keeles nimetatakse ühendusi servadeks.

Minimaalne võrkpuu on puu. See erineb teistest puudest selle poolest, et selles on minimaalne servadele lisatud kaalude summa. Sõltuvalt sellest, milline on graafi välimus, võib olla rohkem kui üks minimaalne läbiv puu. Graafis, kus kõik servad on sama kaaluga, on iga puu minimaalne sirgjooneline puu. Kui kõik servad on erineva kaaluga (s.t. ei ole kahte sama kaaluga serva), on täpselt üks minimaalne sirutuspuu.

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 T

Sellisel 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.