Minimālais aptverošais koks (MST): definīcija grafu teorijā, algoritmi

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.