Išplėstinė paieška
 
 
 
Pradžia>Matematika>Taikomoji diskrečioji matematika
   
   
   
naudingas 0 / nenaudingas 0

Taikomoji diskrečioji matematika

  
 
 
1234567
Aprašymas

Uždavinio sąlyga ir aprašymas, algoritmo aprašymas, programos tekstas, rezultatų pavyzdžiai.

Ištrauka

Uždavinio sąlyga: Duotas orgrafas. Rasti jame stipraus jungumo komponentes.
Uždavinio aprašymas: Reikia iš orentuotojo grafo viršūnių aibės išskirti poaibius, kurie yra stipraus jungumo komponentės t.y. iš kiekvienos viršūnės galima nueiti į likusias komponentės viršūnes ir gryžti iš jų. Viena viršūnė gali priklausyti tik vienai stipraus jungumo komponentei.
Jeigu turim virršūnę iš kurios negalima nueiti į jokią kitą, tai ji irgi yra stipraus jungumo komponentė.

Šį stipraus jungumo komponenčių radimo algoritmą orgrafe sugalvojau pats. Jis remiasi paieškos gilyn orentuotame grafe metodu. Jo veikimo principas toks:
1.Iš grafo viršūnių aibės pašalinamos viršūnės, iš kurių negalim nueiti į jokią kitą. Prieš tai jas įrašome į jungiųjų komponenčių masyvą, nes jos yra stipraus jungumo komponentės.
2.Toliau apdorojam likusias viršūnes.Remiantis paieška gilyn tikriname ar iš nagrinėjamos viršūnės galima nueiti į likusias ir iš jų atgal į nagrinėjamą, jeigu taip, tai turme jungiają komponentę, kurią sudaro šios viršūnės. Jas irgi įrašome į jungiųjų komponenčių masyvą.
Toliau analogiškai nagrinėjamos viršūnės į kurias nepavyko patekti iš nagrinėjamos višūnės ir gryžti atgal.
Matome, kad 2 veiksmas kartosis tiek kartų, kiek jungiųjų komponenčių bus orgrafe, todėl galime panaudoti rekursiją. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2005-02-28
DalykasMatematikos kursinis darbas
KategorijaMatematika
TipasKursiniai darbai
Apimtis6 puslapiai 
Literatūros šaltiniai0
Dydis32.11 KB
AutoriusBritva
Viso autoriaus darbų202 darbai
Metai2004 m
Klasė/kursas0
Mokytojas/Dėstytojaslekt. B.Jarašiūnėnė
Švietimo institucijaKauno Technologijos Universitetas
FakultetasInformatikos fakultetas
Failo pavadinimasMicrosoft Word Taikomoji diskrecioji matematika [speros.lt].doc
 

Panašūs darbai

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Kursiniai darbai
  • 6 puslapiai 
  • Kauno Technologijos Universitetas
  • lekt. B.Jarašiūnėnė
  • 2004 m
Ar šis darbas buvo naudingas?
Taip
Ne
0
0
Pasidalink su draugais
Pranešk apie klaidą