Minimālais aptverošais koks (MST): definīcija grafu teorijā, algoritmi
Uzzini minimālā aptverošā koka (MST) definīciju, piemērus un efektīvākos algoritmus (Kruskal, Prim) grafu teorijā — teorija, pielietojumi un kods.
Daudziem ar grafiku teorijas uzdevumiem būtiska loma ir tam, ko sauc par minimālo aptverošo koku (angļu: Minimum Spanning Tree, MST). Vienkāršā valodā koks ir veids, kā savienot visas grafā esošās virsotnes tā, lai no jebkuras virsotnes uz jebkuru citu būtu tieši viens ceļš. Ja grafu interpretē kā pilsētas, kas savienotas ar ceļiem, tad aptverošais koks nodrošina, ka no katras pilsētas var nokļūt uz katru citu, izmantojot tieši tik daudz ceļu, cik nepieciešams (bez cikliem). Ja katrai malai ir pievienots svars — ceļa izmaksas vai garums — tad minimālais aptverošais koks ir tāds aptverošais koks, kuram ir vismazākā visu malu svaru kopsumma.
Galvenās īpašības
- Ja grafā ir n virsotnes, aptverošajam kokam vienmēr būs tieši n−1 malas.
- MST minimizē malu svaru summu starp visiem iespējamajiem aptverošajiem kokiem.
- Ja visi malu svari ir atšķirīgi (nav divu vienādu svaru), MST ir viennozīmīgs. Ja ir vienādi svari, var būt vairāk nekā viens MST.
- Ja grafā ir nesavienotas komponentes, runā nevis par vienu MST, bet par minimālo aptverošo mežu (minimum spanning forest) — katrai komponentai tiek atrasts savs MST.
- MST definēta tikai bezvirziena (undirected) grafiem; virzienu gadījumā lieto citas konstrukcijas (piem., minimum arborescence — Edmonds algoritms).
Iespējamie principi un īpašības, kas palīdz izprast MST
- Cut (šķērslīnijas) īpašība: ja sadali (cut) grafikā savā starpā šķir divas virsotņu grupas, tad mala ar minimālo svaru, kas šķērso šo sadali, vienmēr var piederēt kādam MST.
- Cikla īpašība: ja grafā ir cikls, tad mala ar lielāko svaru ciklā nekad nevar piederēt MST (ja vien nav vairāku malu ar vienādu maksimuma svaru, tad iespējami varianti).
Populāri algoritmi MST atrašanai
Zemāk ir īss apraksts par trijiem klasiskajiem algoritmiem.
Kruskal algoritms
- Ideja: sakārtot malas pēc svara (no mazākā uz lielāko) un pievienot tās viena pēc otras, ja pievienošana neveido ciklu.
- Izpilde: izmanto savienojumu–meklēšanas struktūru (union-find / disjoint set) lai ātri noteiktu, vai mala savieno divas dažādas komponentes.
- Laika sarežģītība: O(E log E) (bieži raksta kā O(E log V)), jo jāšķiro malas; union-find operācijas gandrīz lineāras ar gandrīz konstantu amortizēto laiku.
Prim algoritms
- Ideja: sākt no kādas virsotnes un pakāpeniski pievienot tuvāko malu, kas savieno jau iekļautas virsotnes ar ārpus tām esošajām.
- Izpilde: izmanto prioritātes rindu (piem., bināro vai Fibonacci heap) lai atrastu minimālo malu, kas paplašina koku.
- Laika sarežģītība: ar bināro kaudzi O(E log V), ar Fibonacci heap O(E + V log V).
Borůvka (Boruvka) algoritms
- Ideja: vienlaikus katrai komponentei izvēlas vislētāko malu, kas to savieno ar citu komponenti; šādi komponentes apvienojas iteratīvi, līdz paliek viens koks.
- Īpaši labi paralelizējas un labi darbojas uz lieliem, plāniem grafiem.
- Laika sarežģītība: O(E log V) vai labāk atkarībā no realizācijas.
Praktiski ieviešanas padomi
- Kruskal ir vienkāršs un ērtāks, ja malas jau pieejamas kā saraksts un var ātri sakārtot.
- Prim ir efektīvāks gadījumos, kad grafu reprezentē ar tuvuma sarakstiem un kad E ir liels salīdzinājumā ar V.
- Union-find ar ceļa saplacināšanu (path compression) un rangiem nodrošina gandrīz konstanta laika savienojumu un meklēšanu.
- Jādomā par to, kā tiek risinātas situācijas ar vienādiem svariem — ja nepieciešama determinisma, jāieviļ papildu tie-breaker noteikumi.
Dažas papildu tēmas un varianti
- Maksimālais aptverošais koks: ja jānopelna maksimāla kopējā svara summa, var vienkārši mainīt salīdzināšanas kārtību (sakārtojot malas dilstošā secībā) un lietot Kruskal vai Prim.
- Otrā labākā MST (second-best MST): ja grib atrast nākamo labāko risinājumu, parasti analizē malu nomaiņu MST iekšienē, lai atrastu minimālo papildus pieaugumu svarā.
- MST nesavienotam grafam: rezultāts ir minimālais aptverošais mežs (minimum spanning forest) — MST katrai komponentai.
- Direkcionēti grafi: MST kā tāds nav definēts; analogs uzdevums ir minimālā arborescence, risināms ar Edmonds algoritmu.
Praktiskās pielietošanas jomas
- Tīklu dizains: optisko vai elektroapgādes tīkli ar minimālām uzstādīšanas izmaksām.
- Klustering: datu grupēšanā MST var izmantot, lai atrastu dabiskas grupas vai kā pamatmetodi hierarhiskai klasterizācijai.
- Grafu vizualizācija un attēlu segmentēšana.
- Tuvākais ceļš aptuveni: MST lieto kā daļu no heuristikām, piemēram, 2-approksimācijas TSP risinājumam.
Vienkāršs piemērs
Jāņem trīs virsotnes A, B un C ar malām AB=1, BC=2, AC=3. MST satur malas AB un BC (kopā 3), jo malas AB+AC = 4 vai AC+BC = 5 būtu dārgākas. Ja AB un AC būtu vienādi (piem., AB=AC=1, BC=2), tad iespējami divi MST ar vienādu kopējo svaru: {AB, BC} vai {AC, BC}.
Minimālais aptverošais koks ir fundamentāls rīks gan teorētiskos uzdevumos, gan praktiskos inženiertehniskos risinājumos. Izvēle starp algoritmiem bieži balstās uz grafu īpašībām (E vs V), pieejamajiem datu struktūras īstenojumiem un prasībām pēc determinisma vai paralelizācijas.
Plānveida grafika minimālais garenkoks. Katrai malai ir norādīts tās svars, kas šeit ir aptuveni proporcionāls tās garumam.
Minimālā garenkoka atrašana
Pirmais mēģinājums
Var būt ļoti vienkārši izveidot algoritmu, kas atklās minimālo garenkoku:
funkcija MST(G,W): T = {} kamēr T neveido aptverošu koku: atrod minimālo svērto malu E, kas ir droša T T T = T union {(u,v)} return TŠajā gadījumā "drošs" nozīmē, ka malas iekļaušana neveido grafikā ciklu. Cikls nozīmē sākt no kādas virsotnes, doties uz vairākām citām virsotnēm un atkal beigt sākuma punktā, neizmantojot vienu un to pašu malu divas reizes.
Vēsture
Čehu zinātnieks Otakars Borůvka 1926. gadā izstrādāja pirmo zināmo algoritmu minimālā garenkoka atrašanai. Viņš vēlējās atrisināt problēmu, kā atrast efektīvu Morāvijas pārklājumu ar elektrību. Mūsdienās šis algoritms ir pazīstams kā Borůvkas algoritms. Mūsdienās parasti izmanto divus citus algoritmus. Vienu no tiem 1930. gadā izstrādāja Vojtěhs Jarņiks (Vojtěch Jarník), bet 1957. gadā praksē ieviesa Roberts Klejs Prīms (Robert Clay Prim). Edsgers Vībe Dijkstra to no jauna atklāja 1959. gadā un nosauca par Prim algoritmu. Otru algoritmu sauc par Kruskala algoritmu, un to 1956. gadā izgudroja Džozefs Kruskals. Visi trīs algoritmi ir alkatīgi un darbojas polinoma laikā.
Līdz šim ātrāko minimālā izstiepšanās koka algoritmu izstrādāja Bernards Šazele. Algoritma pamatā ir mīkstais kaudze, kas ir aptuvena prioritāšu rinda. Tā darbības laiks ir O(m α(m,n)), kur m ir malu skaits, n ir virsotņu skaits un α ir klasiskā Ackermann funkcijas apgrieztā funkcija. Funkcija α aug ārkārtīgi lēni, tāpēc praktiskiem mērķiem to var uzskatīt par konstanti, kas nav lielāka par 4; tādējādi Šazeles algoritms prasa ļoti tuvu lineārajam laikam.
Kāds ir ātrākais iespējamais algoritms šai problēmai? Tas ir viens no senākajiem atklātajiem jautājumiem datorzinātnē. Skaidrs, ka pastāv lineāra apakšējā robeža, jo mums ir jāpārbauda vismaz visi svarus. Ja malu svari ir veseli skaitļi ar ierobežotu bitu garumu, tad ir zināmi deterministiski algoritmi ar lineāru darbības laiku. Vispārējiem svariem ir zināmi randomizēti algoritmi, kuru paredzamais darbības laiks ir lineārs.
Problēmu var risināt arī sadalītā veidā. Ja katru mezglu uzskata par datoru un neviens mezgls nezina neko citu, kā tikai savas savienotās saites, joprojām var aprēķināt sadalīto minimālo izstiepšanās koku.
Jautājumi un atbildes
J: Kas ir minimālais izstiepšanās koks grafu teorijā?
A: Grafu teorijā minimālais aptverošais koks ir koks, kas minimizē kopējo svaru, kas piešķirts malām.
J: Kas ir koks grafu teorijā?
A: Grafu teorijā koks ir veids, kā savienot visas virsotnes kopā tā, lai no jebkuras virsotnes uz jebkuru citu koka virsotni būtu tikai viens ceļš.
J: Kāds ir mērķis izvēlēties ceļus grafu teorijas scenārijā, kurā attēlotas pilsētas?
A: Grafu teorijas scenārijā, kurā attēlotas pilsētas, ceļu atlases mērķis ir nodrošināt, lai katru pilsētu varētu sasniegt no jebkuras citas pilsētas, bet lai no vienas pilsētas uz citu būtu iespējams nokļūt tikai pa vienu ceļu.
J: Vai grafam var būt vairāk nekā viens aptverošais koks?
A: Jā, grafam var būt vairāk nekā viens aptverošais koks.
J: Kāda ir atšķirība starp minimālo garenkoku un citiem grafu teorijas kokiem?
A: Minimālais sadalījuma koks minimizē kopējo svaru, kas piesaistīts malām, bet citiem kokiem šī īpašība nepiemīt.
J: Kas grafu teorijā ir malas?
A: Grafu teorijā malas ir savienojumi starp divām virsotnēm.
Vai grafā var būt vairāk nekā viens minimālais izstiepšanās koks ar dažādu svaru malām?
A: Jā, atkarībā no tā, kāds izskatās grafiks, var būt vairāk nekā viens minimālais sadalījuma koks.
Meklēt