Diskrečioji matematika - uždavinio analizė

Sudaryti programą minimalaus padengiančio medžio grafe su teigiamais briaunų svoriais ieškojimo uždavinio spręsti Kraskalo metodu.
Kraskalo metodas yra naudojamas rasti minimalų dengiantį medį grafe, kuris yra jungusis pilnasis grafas, o visų jo briaunų svoriai skirtingi. Tokiu atveju, bus rastas tik vienas minimalus dengiantis medis.
Privalomai turi būti patenkinta tik viena iš anksčiau išvardintų sąlygų – t. y. grafas turi būti jungusis. Kitos dvi sąlygos gali būti netenkinamos, tačiau sprendiniai vistiek bus.
Jei grafas yra jungusis, bet nepilnasis, tuomet galima įsivaizduoti, kad grafas yra jungusis, o nesančių briaunų ilgiai yra begalybės.
Jei grafas yra jungusis ir jame yra briaunų su vienodais svoriais, tuomet egzistuoja keli uždavinio sprendiniai.
Kraskalo metodo teorema: kai G = (V,U) jungusis pilnasis grafas ir visų jo briaunų ilgiai (svoriai) skirtingi, tuomet egzistuoja vienintelis trumpiausias dengiantis medis, kuris konstruojamas taip: “iš likusių grafo G briaunų randame trumpiausią briauną ir ją įtraukiame į medį, jei ši briauna neiššaukia ciklo su anksčiau paimtom medžio briaunom”.
1. Iš dar neįtrauktų į medį briaunų imama trumpiausia, t. y. randame reikšmę „min“;
2. Tikrinama ar ši briauna neiššaukia ciklo su jau įtrauktom į minimalų dengiantį medį briaunom. Tai nustatoma patikrinant ar tikrinamos briaunos galai priklauso skirtingom jungiosiom komponentėm. Jei priklauso, tuomet tą briauną įtraukiame į tam tikslui sukurtą jungiųjų komponenčių masyvą, o jei ne – neįtraukiame. Sujungę dvi briaunas, jas apjungiame į vieną jungiąją komponentę bei tikriname sekančią trumpiausią briauną. Tai kartojame tol kol apeiname visas briaunas. Briaunos, kurios pateko į jungiųjų komponenčių masyvą ir sudaro trumpiausią dengiantį medį.
Kraskalo metodo algoritmas yra godusis.
Kraskalo metodo algoritmo aprašas:
if s [u] ¹ s [v] then {briauna (u, v) neiššaukia ciklo su anksčiau paimtom medžio briaunom} begin
briauną (u, v) įtraukti į medį.
{perskaičiuoti jungiųjų komponenčių masyvo s elementus}
l := s [u]; k := s [v];
for i := 1 to n do
if s [i] = k then s [i] := l;
end;
2. ALGORITMO, NAUDOJANT KRASKALO METODĄ, REALIZACIJA
Algoritmo...

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!