Diskrečiosios struktūros. Kursinis darbas 2 var

Ištrauka

TAIKOMOSIOS INFORMATI KOS KATEDRA 
DISKREČIOSIOS STRUKTŪ ROS (P170B008)
KURSINIS DARBAS
Užduoties nr. B14

Turinys
1. Užduotis (nr. B14) 3
2. Užduoties analizė 3
3. Programos algoritmo aprašymas 5
4. Programos tekstas 5
5. Testavimo pavyzdžiai 8
PIRMAS TESTAS 8
ANTRAS TESTAS 9
TREČIAS TESTAS 10
6. Išvados 11
7. Literatūros sąrašas 11

1. Užduotis (nr. B14)
Sudaryti algoritmą ir programą randančią l-viršūninius grafo G indukuotus pografius, turinčius Oilerio ciklą
2. Užduoties analizė
Norint, kad grafas mums tiktu jis privalo būti oilerio ciklu bei jungiuoju grafu.
Jungusis grafas – tai grafas kurio jungiųjų komponenčių kiekis yra lygus 1. Kitaip sakant tai yra
grafas per kurio visas viršūnęs galime praeiti neatleidę rankos piešdami (žinoma kertant tas pačias briaunas).
Oilerio ciklas – kad tai būtu oilerio ciklas, tai privalo būti ir jungusis grafas. Oilerio ciklas suteikia
mums galimybę praeiti pro visas viršūnęs, per briaunas eidami tik vieną kartą bei atsidurtumėme ten kur
pradėjome.
Uždavinys. Duotas grafas G = (V,U) taip pat įrašome ranka į grafinę vartotojo sąsaja skaičių, kuris
nurodys viršūnių skaičių naujiesiams grafams. Vėliau algoritmas patikrins ar grafas yra jungus ir ar
tenkina patikrinimą, kuris patikrina ar grafas yra oilerio ciklas.
Metodo idėja. Mes pradžioje programos viduje turime duomenis apie grafą, tai yra jo viršūnęs (V)
bei briaunas (U). Toliau paleidę programą mes įrašome viršūnių skaičių. Vėliau algoritmas sudarys visus
įmanomus variantus su tomis įvestomis viršūnėmis. Vėliau algoritmas sudarys kiekvienam grafui po V
masyvą bei U masyvą, tai yra viršūnių bei briaunų masyvą. Poto kiekvienai iš jų vyks tikrinimas, pirmasis
algoritmas per kurį įvyks patikrinimas yra ar grafas yra jungusis. Algoritmas naudoja metodus iš
bibliotekos, kurie randa atstumą iki visų viršūnių, vėliau patikriname ar yra „Inf“ (neįmanomų, begalinių)
viršūnių, jeigu yra, nusprendžiame, kad grafas yra nejungus. Kitas patikrinimas yra ar tai yra oilerio
ciklas, algoritmas veikia taip, sudeda visų briaunų laipsnius ir žiūri ar jie yra lyginiai, jeigu taip, vyksta
galutinis patikrinimas, ar tai yra jungusis grafas ir ar tai yra oilerio ciklas. Jeigu tai yra tiesa, atspausdina
grafą.