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.