Išplėstinė paieška
 
 
 
Pradžia>Matematika>Diskrečiosios struktūros
   
   
   
-1
naudingas +2 / nenaudingas -3

Diskrečiosios struktūros

  
 
 
1234567891011121314151617
Aprašymas

Uždavinio sąlyga ir jo analizė: Sudaryti algoritmą ir programą Oilerio ciklo grafe suradimo uždaviniui spręsti. Algoritmo aprašymas. Oilerio ciklo konstravimo algoritmas. Rasti: sukonstruoti Oilerio maršrutą. Programos tekstas. Testinių uždavinio duomenų ir sprendinių variantai. Pirmas testinis pavyzdys. Įvestos briaunos. Rezultatas. Antras testinis pavyzdys. Įvestos briaunos. Rezultatas. Trečias testinis pavyzdys. Rezultatas.

Ištrauka

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. ...

Rašto darbo duomenys
Tinklalapyje paskelbta2009-08-10
DalykasMatematikos kursinis darbas
KategorijaMatematika
TipasKursiniai darbai
Apimtis15 puslapių 
Literatūros šaltiniai0
Dydis49.88 KB
Autoriuseurazz
Viso autoriaus darbų12 darbų
Metai2003 m
Klasė/kursas2
Mokytojas/DėstytojasPlukas
Švietimo institucijaKauno Technologijos Universitetas
FakultetasInformatikos fakultetas
Failo pavadinimasMicrosoft Word Diskreciosios strukturos [speros.lt].doc
 

Komentarai

Komentuoti

 

 
[El. paštas nebus skelbiamas]

 
 
  • Kursiniai darbai
  • 15 puslapių 
  • Kauno Technologijos Universitetas / 2 Klasė/kursas
  • Plukas
  • 2003 m
Ar šis darbas buvo naudingas?
Taip
Ne
+2
-3
Pasidalink su draugais
Pranešk apie klaidą