Diskrečiosios struktūros

KAUNO TECHNOLOGIJOS UNIVERSITETAS INFORMATIKOS FAKULTETAS DISKREČIOSIOS STRUKTŪROS Kursinis darbas Kaunas 2003 Turinys 1. Turinys 2 2. Uždavinio sąlyga ir jo analizė 3 3. Algoritmo aprašymas 4 4. Programos tekstas 5 5. Testinių uždavinio duomenų ir sprendinių variantai 15 • Pirmas testinis pavyzdys 15 • Antras testinis pavyzdys 16 • Trečias testinis pavyzdys 17 1. Uždavinio sąlyga ir jo analizė • 18. Sudaryti algoritmą ir programą Oilerio ciklo grafe suradimo uždaviniui spręsti. • Apibrėžimas. Maršrutas (kelias), apeinantis visas grafo briaunas po vieną kartą, vadinamas Oilerio maršrutu. Jei pradinė ir galinė maršruto viršūnės nesutampa, tai toks maršrutas vadinamas Oilerio grandine, priešingu atveju – Oilerio ciklu. Teorema. Būtina ir pakankama sąlyga, kad grafas G turėtų Oilerio maršrutą yra: 1) G turi būti jungusis, 2) visų jo viršūnių laipsniai turi būti arba lyginiai, arba G turi turėti tik dvi nelyginio laipsnio viršūnes. Pirmuoju atveju grafas turi Oilerio ciklą, o antruoju – grandinę, prasidedančią ir besibaigiančią nelyginio laipsnio viršūnėse. Būtinumas. Tarkime G – Oilerio grafas. Oilerio ciklas eidamas per kiekvieną viršūnę, patenka į viršūnę viena briauna, o išeina – kita briauna. Tai reiškia, kad kiekviena grafo G viršūnė incidentiška lyginiam Oilerio ciklo briaunų skaičiui. Kadangi Oilerio ciklas apima visas grafo briaunas, tai reiškia, kad grafas yra jungusis ir, kad kiekvienos grafo viršūnes laipsnis yra lyginis. Pakankamumas. Tarkime, kad visų grafo G viršūnių laipsniai yra lyginiai. Pradėkime kelione iš viršūnės v1 ir, eidami grafo briaunomis, laikysimės taisyklės: „niekada neiti ta pačia briauna“. Tai tolygu taisyklei: „pereitą briauną – ištriname“. Atėję į bet kurią viršūnę v ≠ v1, iš jos visada galėsime išvykti, nes viršūnės v laipsnis yra lyginis. Jei patekome į viršūnę, iš kurios negalime išvykti, tai reiškia, kad esame pradinėje kelio viršūnėje v1. Vadinasi mūsų kelias sudarė ciklą P1. Pašalinę šį ciklą iš grafo G, gausime grafą G`, kurio kiekvienos viršūnės laipsnis yra lyginis, arba lygus nuliui. Jei visų viršūnių laipsniai yra lygūs nuliui, tai reiškia, kad P1 yra Oilerio ciklas. Priešingu atveju nagrinėsime grafą G`. Kadangi grafas G yra jungusis grafas, tai grafai P1 ir G` turi bent vieną bendrą viršūnę v2. pradėję kelionę grafe G` iš viršūnės v2 ir laikydamiesi tos pačios taisyklės, sukonstruosime ciklą P2. Iš ciklų P1 ir P2 sukonstruosime bendrą ciklą taip: iš viršūnės v1 ciklo P1 briaunomis nukeliausime į viršūnę v2, po to apeisime ciklą P2 ir po to iš viršūnės v2 ciklo P1, briaunomis ateisime į viršūnę v1. Pašalinkime šį ciklą iš grafo G. Jei po ciklo pašalinimo grafas yra tuščiasis, tai šis ciklas yra Oilerio ciklas. Priešingu atveju, šiame grafe atliksime analogiškus veiksmus. Ir taip elgsimės iki sukonstruosime ciklą, einantį per visas grafo G briaunas. 2. Algoritmo aprašymas Oilerio ciklo konstravimo algoritmas Duota: jungusis grafas G, kurio visų viršūnių laipsniai yra arba lyginiai, arba G turi dvi nelyginio laipsnio viršūnes. Tarkime, kad grafas G nusakytas gretimumo struktūra: N(v) – tai aibė viršūnių gretimų viršūnei v. Rasti: sukonstruoti Oilerio maršrutą. Įrodyme pateiktą Oilerio maršruto konstravimą patogu realizuoti naudojant du stekus: STEK ir Oiler. Priminsime, kad stekas, tai tiesinis sąrašas, kuriame naujo elemento patalpinimas ir pašalinimas atliekamas viename sąrašo gale. Kitaip dar stekas vadinamas sąrašo LIFO (nuo angliškų žodžių „last in first out“ (paskutinis į steką – pirmas iš jo)). Steką patogu organizuoti vienmačiu masyvu STEK[1..n]. Jį charakterizuoja vienas parametras – rodyklė „top“, kuri reiškia paskutinio elemento sąraše adresą. Stekas tuščias {žymime STEK:=  } Elemento patalpinimas į steką {žymime STEK  v} Elemento šalinimas iš steko { žymime v  STEK} Elemento nuskaitymas iš steko {žymime v: = top(STEK)} Algoritmo veikimo principas. Tarkime v1 yra viršūnė, iš kurios pradėsime brėžti Oilerio ciklą. Šią viršūnę patalpinkime i steką STEK. Iš viršūnės v1 keliausime per grafą, talpindami kelio viršūnes į steką STEK ir ištrindami kelio briaunas. Jei atėjome į viršūnę, iš kurios negalime išeiti, tai reiškia, kad esame pradinėje kelio viršūnėje (jei grafo G visų viršūnių laipsniai buvo lyginiai) arba kitoje nelyginio laipsnio viršūnėje (jei v1 laipsnis buvo nelyginis). Šią viršūnę patalpinsime į steką Oiler ir bandysime keliauti iš priešpaskutinės kelio viršūnės. Kelionė galima, nes iš grafo G pašalinome ciklą, einantį per viršūnę v1, ir likusių viršūnių laipsniai yra lyginiai arba lygūs nuliui. Taip elgsimės iki stekas STEK taps tuščias. Tada viršūnės patalpintos steke Oiler ir nusakys Oilerio maršrutą. begin STEK := ; Oiler := ; v := bet kur grafo viršūnė, jei visų grafo viršūnių laipsniai yra lyginiai arba nelyginio laipsnio viršūnė, jei grafas turi dvi nelygino laipsnio viršūnes. STEK  v; while STEK ≠  do begin v := top(STEK); { v = viršutinis steko elementas; rodyklė top neperskaičiuojama} if N(v) ≠  then begin u := pirmoji aibės N(v) viršūnė; STEK  u; {pašalinti (v, u) briauną} N(v) := N(v) \ {u}; N(u) := N(u) \ {v}; end; else { N(v) = } begin v  STEK; Oiler  v; end; end; end; 3. Programos tekstas NamuDarbas.h //--------------------------------------------------------------------------- #ifndef NamuDarbasH #define NamuDarbasH //--------------------------------------------------------------------------- #include

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!