Oilerio ciklas

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

Kiniškas hieroglifas su pažymėtu Oilerio keliu

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

1. Kostas Plukas, Eugenijus Mačikėnas, Birutė Jarašiūnienė, Irena Mikuckienė „Taikomoji diskrečioji matematika“, Kaunas, „Technologija“, 2007
2. В. Липский „Комбинаторика для программистов“, Москва, „Мир“, 1988
3. 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]

Vikiteka: Oilerio maršrutas – vaizdinė ir garsinė medžiaga