Lygiagretieji algoritmai

Grafų teorija. Minimalaus dengiančio medžio radimas. Algoritmų sudarymo taisyklės. Primo algoritmas. Formulavimas. Primo algoritmas. Nuosekliojo algoritmo sudėtingumas. Lygiagrečiojo algoritmo sudėtingumas. Analizė. Bandymai ir jų rezultatai. Duomenys. Grafikai. Išvados.

Tegul turime viršūnių aibę } ir briaunų aibę , briauna yra viršūnių pora . Paprasčiausias grafo pavyzdys: žemėlapis.
Grafų teorijoje briaunoms gali būti priskirti skaičiai, įvertinantys atstumą, laiką, svorį ir panašius požymius. Toks grafas yra vadinamas svertiniu. Briaunos įvertį žymėsime ( svoris).
Viršūnių seka yra vadinama k – keliu, jei sekos visos gretimos viršūnės yra sujungtos briaunomis. Ciklu vadiname k – kelią, kuriame pradinė viršūnė sutampa su , o kitos viršūnės kelyje nesikartoja.
Kelio p ilgiu vadinsime skaičių .
Grafas, vadinamas jungiu, jei tarp bet kurių jo viršūnių egzistuoja kelias.
Grafų teorijoje yra sprendžiami 5 pagrindiniai uždaviniai. Tačiau neminint kitų uždavinių, mes paminėsime tik tą kurį mums reikia išspręsti. Tas uždavinys vadinamas minimaliuoju dengiančiuoju medžiu. Jo esmė: šis uždavinys dažnai sutinkamas planuojant komunikacinius tinklus( kompiuterinis tinklas, jungiantis visus įmonės kompiuterius). Tokį tinklą vaizduojame grafu, kurio viršūnių aibę V sudaro asmeniniai kompiuteriai, darbo stotys ir serveriai, o briaunų aibę E sudaro jungtys, jungiančios šiuos kompiuterius. Aišku, gautasis grafas turi būti jungiu, tik tada visi darbuotojai galės keistis informacija. Taip pat siekiame, kad komunikacinių linijų kaina būtų minimali, todėl reikia mažinti briaunų.

Tegul G = (V,E) yra jungusis svertinis grafas. Medis yra jungusis grafas, kuriame nėra ciklų. Grafo G dengiančiuoju medžiu vadinsime medį , kurios briauna yra grafo G briaunų aibės poaibis. Aišku, kad grafo dengiantysis medis nebūtinai yra vienintelis.
Uždavinys pasunkėja, kai grafas G yra įvertintasis. Tada reikia rasti minimalų dengiantįjį medį T, kurio briaunų svoris yra mažiausias. ...