Lygiagretieji algoritmai

3.5 Analizė 5
4. Bandymai ir jų rezultatai 5
4.1 Duomenys 5
4.2 Grafikai 7
4.3 Išvados 8
4.4 Literatūra 8
2. Grafų teorija
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ų.
2.1 Minimalaus dengiančio medžio radimas
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.
2.2 Algoritmų sudarymo taisyklės
Turime neorientuotą įvertintąį jungų grafą G = (V,E). Visos briaunos skirstomos į tris poaibius :
• mėlynas briaunas , priklausančias pasirinktam minimaliam dengiančiam medžiui
• raudonas briaunas , priklausančias nei vienam minimaliam dengiančiam medžiui
• baltas briaunas , kurių priklausomumas dengiančiam minimaliam medžiui dar nenustatytas.
3. Primo algoritmas
3.1 Formulavimas
Algoritmas priklauso godžiųjų...

Daugiau informacijos...

★ Klientai rekomenduoja

Šį rašto darbą rekomenduoja mūsų klientai. Ką tai reiškia?

Mūsų svetainėje pateikiama dešimtys tūkstančių skirtingų rašto darbų, kuriuos įkėlė daugybė moksleivių ir studentų su skirtingais gabumais. Būtent šis rašto darbas yra patikrintas specialistų ir rekomenduojamas kitų klientų, kurie po atsisiuntimo įvertino šį mokslo darbą teigiamai. Todėl galite būti tikri, kad šis pasirinkimas geriausias!