Minimālais izstiepšanās koks
Vairākas grafiku teorijas problēmas tiek sauktas par minimālo garenisko koku. Grafu teorijā koks ir veids, kā savienot visas virsotnes kopā tā, lai no jebkuras virsotnes uz jebkuru citu koka virsotni būtu tieši viens ceļš. Ja grafiks attēlo vairākas pilsētas, kas savienotas ar ceļiem, var izvēlēties tādu ceļu skaitu, lai no katras pilsētas var nokļūt uz katru citu, bet lai no vienas pilsētas uz citu būtu tikai viens ceļš.
Grafam var būt vairāk nekā viens caurviju koks, tāpat kā var būt vairāk nekā viens veids, kā izvēlēties ceļus starp pilsētām.
Lielākoties grafikiem ir svērtais svars; katram savienojumam starp divām pilsētām ir noteikts svars: ceļošana pa attiecīgo ceļu var izmaksāt dārgāk vai viens savienojums var būt garāks par otru, un tas nozīmē, ka ceļošana pa šo savienojumu aizņem vairāk laika. Grafu teorijas valodā savienojumus sauc par malām.
Minimālais šķērskoks ir koks. Tas atšķiras no citiem kokiem ar to, ka tas minimizē malām pievienoto svaru kopsummu. Atkarībā no grafika izskata var būt vairāk nekā viens minimālais sadalījuma koks. Grafā, kurā visām malām ir vienāds svars, katrs koks ir minimālais koks. Ja visām malām ir atšķirīgs svars (tas ir, nav divu malu ar vienādu svaru), ir tieši viens minimālais aptverošais koks.
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.
