Išplėstinė paieška
 
 
 
Pradžia>Matematika>Diskrečioji matematika (6)
   
   
   
-4
naudingas 0 / nenaudingas -4

Diskrečioji matematika (6)

  
 
 
12345678910111213141516171819
Aprašymas

Grafų kursinis darbas. Uždavinio sąlyga: Sudaryti programą, minimalaus padengiančio medžio grafe su teigiamais briaunų svoriais, ieškojimo uždavinį spręsti Kraskalo metodu. Algoritmo, naudojant Kraskalo metodą, realizacija. Programos kodas. Programos vykdymas.

Ištrauka

Uždavinio sąlyga:
Sudaryti programą minimalaus padengiančio medžio grafe su teigiamais briaunų svoriais ieškojimo uždavinio spręsti Kraskalo metodu.
Analizė:
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".
Pagal teoremą, naudojant Kraskalo metodą, minimalus dengiantis medis yra randamas naudojant dvi sąlygas:
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: ...

Rašto darbo duomenys
Tinklalapyje paskelbta2008-06-09
DalykasMatematikos kursinis darbas
KategorijaMatematika
TipasKursiniai darbai
Apimtis16 puslapių 
Literatūros šaltiniai3
Dydis23 KB
AutoriusDonatas
Viso autoriaus darbų2 darbai
Metai2008 m
Klasė/kursas1
Mokytojas/DėstytojasLekt. Birutė Jarašiūnienė
Švietimo institucijaKauno Technologijos Universitetas
FakultetasInformatikos fakultetas
Failo pavadinimasMicrosoft Word Diskrecioji matematika (6) [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Kursiniai darbai
  • 16 puslapių 
  • Kauno Technologijos Universitetas / 1 Klasė/kursas
  • Lekt. Birutė Jarašiūnienė
  • 2008 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
-4
Pasidalink su draugais
Pranešk apie klaidą