Minimaalne toespuu: Kruskali ja Primi algoritm

Ühenda kõik punktid võimalikult väikese teede kogupikkusega. Kruskali algoritm vaatab teid lühimast alates ja jätab kõrvale iga tee, mis tekitaks tsükli. Primi algoritm kasvatab punktist A üht võrku, valides alati sellest väljuvaist teedest lühima. Vaata kummagi algoritmi samme: leht põhjendab iga tee valimist või kõrvale jätmist. Punkte lohistades moodustub puu uuesti.

Näidisarvutus — Minimaalne toespuu: Kruskali ja Primi algoritm

Võimalikud teed n punkti vahel	66
Teid igas toespuus	11
Minimaalne toespuu	199,04 km
Lähima naabri marsruut punktist A	220,44 km
Marsruudi lisapikkus	10,76%
Suurim ümbersõit puul, C–E: mööda puud / otse	4,23×

Need on väärtused, mida kalkulaator lehe avamisel näitab. Muuda ülal mõnda sisendit, et need ümber arvutada.

Interaktiivse simulatsiooni laadimine...

Õppetund

Teooria — Minimaalne toespuu: Kruskali ja Primi algoritm

Punktihulga toespuu on teede hulk, mis ühendab kõik punktid omavahel ega sisalda tsüklit; n punktiga toespuul on alati n − 1 teed. Minimaalne toespuu on väikseima kogupikkusega toespuu. Lõige jaotab punktid kahte rühma. Tee ületab lõiget, kui selle otspunktid asuvad eri rühmades. Steineri puu võib kasutada ka ristmikke, mida algses punktihulgas pole.

Mida iga sümbol tähendab

n: punktide arv
w(u, v): sirge tee pikkus punktist u punkti v, km
S: lõike ühel poolel olevad punktid; Primi algoritmis seni ehitatud võrk

Eeldab: Teed on sirged ja nende maksumus võrdub pikkusega; ühendada võib iga punktipaari. Kui ükski kaks kaugust pole võrdsed, on minimaalne toespuu ühene. Võrdsete kauguste korral, nagu kolmnurgas ja ruudus, võib väikseima pikkusega puid olla mitu ning algoritmid võivad valida eri puud.

Lühim üle lõike, mitte lähim siit 🖖

Vajuta Kaksteist küla ja vaata Kruskali algoritmi sammhaaval. See vaatab 66 võimalikku teed lühimast alates. K–L pikkusega 13,89 km valitakse kohe, C–D ja B–C aga jäetakse kõrvale, sest punasega joonistatud rada juba ühendab nende otspunkte. Seejärel vali Prim, mis kasvatab punktist A üht võrku. Teed valitakse teises järjekorras, K–L päris viimasena. Kõrvale jäävad samad kaks teed ning tulemuseks on needsamad 11 teed kogupikkusega 199,04 km. Mõlemad algoritmid järgivad lõike omadust: jaota punktid ükskõik kuidas kahte rühma. Kui ühepikkuseid teid pole, kuulub rühmadevaheline lühim tee minimaalsesse toespuusse. Oletame, et see puuduks. Puu rada kõnealuse tee otspunktide vahel peab ületama sama lõike mõne pikema tee kaudu; neid teid vahetades saaksime lühema puu. Primi varjutatud võrk moodustab igal sammul ühe sellise lõike poole. Nüüd vajuta Lähim naaber. See erineb Primi algoritmist vaid ühe valiku poolest: vaadatakse kogu võrgu asemel üksnes viimati külastatud külast väljuvaid teid. Kolmandal sammul valitakse D–F pikkusega 17,96 km, kuigi lõiget ületab A–C pikkusega 17,67 km. Algoritm jätab A–C veel seitse korda valimata ja lõpetab 10,76% pikema tulemusega. Ülesande esimesena lahendanud Otakar Borůvka sõnastas selle 1926. aastal Lõuna-Morava elektrivõrgu tarvis punktidele, mille „omavahelised kaugused on erinevad”. Just sel tingimusel ei saa Kruskal ja Prim anda erinevat tulemust.

Lühim võrk ei taga lühikesi sõite 🖖

Vajuta Linnad ringis. Kümme linna paiknevad ümber järve ning puu koosneb kaldale rajatud teest, millest üks lõik on välja jäetud: kõige laiem vahe J ja A vahel. Sirgjooneliselt lahutab neid 25,89 km, mööda puud aga 128,30 km ehk 4,96 korda rohkem, sest ühest teise jõudmiseks tuleb läbida kogu võrk. Lilla katkendjoon märgib selle linnapaari. Lohista mõnda linna ja leht leiab uue suurima ümbersõidu. Minimaalne toespuu vähendab teede kogupikkuse miinimumini, kuid ei taga lühikest vahemaad ühegi konkreetse linnapaari vahel. Veel ühe 25,89 km pikkuse tee ehitamisel saaks A-st J-sse sõita otse. Kas see lisatee tasub end ära, sõltub sõitudest ja kuulub lühima tee ülesande alla. Sealt jätkab Dijkstra algoritmi leht.

Ristmik võib puud lühendada, kuid säästu ülempiir pole tõestatud 🖖

Vajuta Kolm linna. Linnad asuvad üksteisest 40 km kaugusel, seega on puu pikkus 80,00 km. Keskel paiknev ristmik, kus kolm teed kohtuvad 120° nurga all, ühendab need 69,28 km teedega. Seda on 13,40% vähem ehk 1 − √3/2. Vajuta Neli linna ruudul: kaks ristmikku säästavad 8,93%. Mine tagasi kolmnurga juurde ja lohista C allapoole, A ja B poole. Kui nurk C juures ületab 120°, liigub ristmik punkti C ning edasi pole ristmikust enam kasu. Parimate ristmike leidmist nimetatakse Steineri puu ülesandeks. Edgar Gilbert ja Henry Pollak püstitasid 1968. aastal hüpoteesi, et võrdkülgne kolmnurk on halvim juht: ühegi tasandi punktihulga Steineri puu ei saa olla lühem kui √3/2 selle minimaalse toespuu pikkusest. Du ja Hwang avaldasid 1990. aastal tõestuse. Innami ja kolm kaasautorit esitasid 2010. aastal tõendeid, et selle võtmesamm ei kehti. Ivanov ja Tuzhilin, kes olid lünkadele osutanud juba 2002. aastast, kirjutasid 2012. aastal, et hüpotees on endiselt lahtine. Ka 2025. aasta Steineri puude lahendamata ülesannete kogumikus on see jätkuvalt lahtine. Pole teada, kas mõne punktipaigutuse puhul saab säästa rohkem kui kolmnurga 13,40%.

Ülesanne täielikult lahendatud

Kaks ristmikku ruudus 4 sammu
Kus ristmikud paiknevad ja kui palju teed kulub? Vajuta Neli linna ruudul. Linnad asuvad 40 km küljega ruudu tippudes, toespuu pikkus on 120,00 km ja ristmikega võrgu pikkus 109,28 km. Leia täpne pikkus ning kontrolli esimest pähetulevat oletust: läbi keskpunkti kulgevat X-i.

Ava see ülesanne tööriistas
1. Lühima võrgu ristmikul kohtuvad kolm teed 120° nurga all. Muidu ei tasakaalustaks neid mööda suunatud ühikvektorid üksteist ning ristmiku nihutamine nende summa suunas vähendaks kogupikkust.
  
  $\overset{u}{^}_{1} + \overset{u}{^}_{2} + \overset{u}{^}_{3} = 0 ⟺ ∠ (\overset{u}{^}_{i}, \overset{u}{^}_{j}) = 12 0^{\circ}$
2. Paiguta mõlemad ristmikud ruudu keskpunkti läbivale sirgele. Kumbki teenindab kaht lähimat tippu ning ristmikke ühendab keskmine tee. Iga haru kohtub keskmise teega 120° nurga all, seega moodustab haru selle tee sirgega 60° nurga. Külgsuunas tuleb läbida pool küljepikkust ehk 20 km. Haru pikkus on seega 20/sin 60° ja teesuunaline ulatus 20/tan 60°.
  
  $ℓ = \frac{20}{sin 6 0 ^{\circ}} = \frac{40}{3} = 23.094 km, a = \frac{20}{tan 6 0 ^{\circ}} = 11.547 km$
3. Neli haru ning nende vahel keskmine tee, mille pikkus on see osa 40 km-st, mida kaks haru ei kata.
  
  $4 ℓ + (40 - 2 a) = 92.376 + 16.906 = 109.282 km = 40 (1 + 3)$
4. X: neli teed tippudest keskpunkti, igaüks poole diagonaali ehk 20√2 km pikkune.
  
  $4 \times 202 = 113.137 km$
Vastus

40(1 + √3) = 109,28 km. Kumbki ristmik asub teenindatavast küljest 11,55 km kaugusel; X-i pikkus on 113,14 km. X on toespuust lühem, kuid ristmikega võrgust pikem, sest selle teed kohtuvad 90°, mitte 120° nurga all. Täpselt sama pikkusega võrke on kaks: lehel näidatu ja selle 90° võrra pööratud variant. Sääst on 1 − (1 + √3)/3 = 8,93%, vähem kui kolmnurga 13,40%.

$1 - \frac{40 ( 1 + 3 )}{120} = 1 - \frac{1 + 3}{3} = 8 . 93%$

Õpitee

Miks on algoritm õige

Allikad (3)

Borůvka's 1926 solution, the first, for the electricity network of southern Moravia, and his statement of the problem for points whose mutual distances are different, both quoted in insight 1: Jaroslav Nešetřil, Eva Milková and Helena Nešetřilová, "Otakar Borůvka on minimum spanning tree problem: Translation of both the 1926 papers, comments, history." Discrete Mathematics 233(1-3), 2001, pp. 3-36. DOI 10.1016/S0012-365X(00)00224-7
The status of the Gilbert–Pollak conjecture after Du and Hwang's 1990 proof, quoted in insight 3: A. O. Ivanov and A. A. Tuzhilin, "The Steiner Ratio Gilbert–Pollak Conjecture Is Still Open: Clarification Statement." Algorithmica 62(1-2), 2012, pp. 630-632. DOI 10.1007/s00453-011-9508-3
That the conjecture is still listed as open, and its statement: the planar Steiner ratio is reached on the equilateral triangle, √3/2: Yana Teplitskaya, "Open problems on Steiner trees and maximal distance minimizers." arXiv:2511.18217 [math], November 2025, §2.2.

42Mathi meeskond · Kontrollitud avaldatud allikate põhjal. Parandused on teretulnud.