Azərbaycan
Deutschland
Lietuva
ශ්රී ලංකාව
Türkiyə
Oilerio maršrutas maršrutas grafe kuriuo galima pereiti visas jo briaunas po vieną kartą Jei tokiu maršrutu grįžtama į p
Oilerio maršrutas
Oilerio maršrutas – maršrutas grafe, kuriuo galima pereiti visas jo briaunas po vieną kartą. Jei tokiu maršrutu grįžtama į pradinę viršūnę, jis vadinamas Oilerio ciklu, jei ne – Oilerio keliu arba Oilerio grandine. Pavadinimai kilę nuo pavardės Leonardo Oilerio, nagrinėjusio istoriškai pirmąjį tokio tipo uždavinį – Septynių Karaliaučiaus tiltų uždavinį.
Egzistavimo sąlygos
Straipsnyje „Solutio problematis ad geometriam situs pertinentis“ Oileris įrodė, kad Oilerio maršrutas neorientuotame grafe egzistuoja tada ir tik tada, kai pastarasis yra jungusis ir turi ne daugiau nei dvi nelyginio laipsnio viršūnes. Be to, jei tokių viršūnių nėra, egzistuoja Oilerio ciklas, o jei yra dvi – Oilerio kelias.
Oilerio maršrutų radimas
Esama įvairių Oilerio maršrutų radimo algoritmų. Vienas iš pirmųjų yra , pasiūlytas 1883 m. Jis remiasi tuo, kad (kol įmanoma) einama briauna, kurią pašalinus grafas išlieka jungusis.
Kitas algoritmas naudoja steką. Jo užrašas pseudokodu, kuris remiasi Pascal programavimo kalba:
{ Iš pradžių kažkokia forma duotas grafas (kintamasis „Grafas“) ir } { reikia rasti Oilerio maršrutą (kintamasis „OilerioMarsrutas“). } { Laikoma, kad jau žinoma, kad grafas turi Oilerio maršrutą. } begin InicializuotiSteka(Stekas); { Iš pradžių abu stekai tušti. } InicializuotiSteka(OilerioMarsrutas); EinVirsune := ParinktiPradineVirsune(Grafas); DetiISteka(Stekas, EinVirsune); while (StekasNeTuscias(Stekas)) do begin EinVirsune := StekoVirsune(Stekas); if (YraGretimuVirsuniu(Grafas, EinVirsune)) then begin Virsune := KuriNorsGretimaVirsune(Grafas, EinVirsune); DetiISteka(Virsune); SalintiBriaunaIsGrafo(Grafas, EinVirsune, Virsune); end else begin EinVirsune := ImtiIsSteko(Stekas); DetiISteka(OilerioMarsrutas, EinVirsune); end; end; end; Algoritmo – O(m), kai m – grafo briaunų skaičius.
Taikymai
Oilerio maršrutai naudojami DNR sekai atkurti iš jos fragmentų.
Išnašos
- Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007
- В. Липский „Комбинаторика для программистов“, Москва, „Мир“, 1988
- Pavel A. Pevzner, Haixu Tang, Michael S. Waterman „An Eulerian path approach to DNA fragment assembly“, „“, August 14, 2001, vol. 98, no. 17, p. 9748-9753 [1]
Papildomam skaitymui
- L. Euler „Solutio problematis ad geometriam situs pertinentis“ // „Commentarii academiae scientiarum Petropolitanae“, t. 8, 1741, p. 128–140 [2]
Autorius: www.NiNa.Az
Išleidimo data:
vikipedija, wiki, lietuvos, knyga, knygos, biblioteka, straipsnis, skaityti, atsisiųsti, nemokamai atsisiųsti, mp3, video, mp4, 3gp, jpg, jpeg, gif, png, pictu, mobilusis, porn, telefonas, android, iOS, apple, mobile telefl, samsung, iPhone, xiomi, xiaomi, redmi, pornografija, honor, oppo, Nokia, Sonya, mi, pc, web, kompiuteris, Informacija apie Oilerio maršrutas, Kas yra Oilerio maršrutas? Ką reiškia Oilerio maršrutas?
Oilerio marsrutas marsrutas grafe kuriuo galima pereiti visas jo briaunas po viena karta Jei tokiu marsrutu grįztama į pradine virsune jis vadinamas Oilerio ciklu jei ne Oilerio keliu arba Oilerio grandine Pavadinimai kile nuo pavardes Leonardo Oilerio nagrinejusio istoriskai pirmajį tokio tipo uzdavinį Septyniu Karaliauciaus tiltu uzdavinį Kiniskas hieroglifas su pazymetu Oilerio keliuEgzistavimo salygosStraipsnyje Solutio problematis ad geometriam situs pertinentis Oileris įrode kad Oilerio marsrutas neorientuotame grafe egzistuoja tada ir tik tada kai pastarasis yra jungusis ir turi ne daugiau nei dvi nelyginio laipsnio virsunes Be to jei tokiu virsuniu nera egzistuoja Oilerio ciklas o jei yra dvi Oilerio kelias Oilerio marsrutu radimasEsama įvairiu Oilerio marsrutu radimo algoritmu Vienas is pirmuju yra pasiulytas 1883 m Jis remiasi tuo kad kol įmanoma einama briauna kuria pasalinus grafas islieka jungusis Kitas algoritmas naudoja steka Jo uzrasas pseudokodu kuris remiasi Pascal programavimo kalba Is pradziu kazkokia forma duotas grafas kintamasis Grafas ir reikia rasti Oilerio marsruta kintamasis OilerioMarsrutas Laikoma kad jau zinoma kad grafas turi Oilerio marsruta begin InicializuotiSteka Stekas Is pradziu abu stekai tusti InicializuotiSteka OilerioMarsrutas EinVirsune ParinktiPradineVirsune Grafas DetiISteka Stekas EinVirsune while StekasNeTuscias Stekas do begin EinVirsune StekoVirsune Stekas if YraGretimuVirsuniu Grafas EinVirsune then begin Virsune KuriNorsGretimaVirsune Grafas EinVirsune DetiISteka Virsune SalintiBriaunaIsGrafo Grafas EinVirsune Virsune end else begin EinVirsune ImtiIsSteko Stekas DetiISteka OilerioMarsrutas EinVirsune end end end Algoritmo O m kai m grafo briaunu skaicius TaikymaiOilerio marsrutai naudojami DNR sekai atkurti is jos fragmentu IsnasosKostas Plukas Eugenijus Macikenas Birute Jarasiuniene Irena Mikuckiene Taikomoji diskrecioji matematika Kaunas Technologija 2007 V Lipskij Kombinatorika dlya programmistov Moskva Mir 1988 Pavel A Pevzner Haixu Tang Michael S Waterman An Eulerian path approach to DNA fragment assembly August 14 2001 vol 98 no 17 p 9748 9753 1 Papildomam skaitymuiL Euler Solutio problematis ad geometriam situs pertinentis Commentarii academiae scientiarum Petropolitanae t 8 1741 p 128 140 2 Vikiteka Oilerio marsrutas vaizdine ir garsine medziaga