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

{ 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 laikinis sudėtingumas – O(m), kai m – grafo briaunų skaičius.

 Taikymai 
Oilerio maršrutai naudojami bioinformatikoje DNR sekai atkurti iš jos fragmentų.Pavel A. Pevzner, Haixu Tang, Michael S. Waterman „An Eulerian path approach to DNA fragment assembly“, „Proceedings of the National Academy of Sciences of the United States of America“, August 14, 2001, vol. 98, no. 17, p. 9748-9753 

 Išnašos 

 Papildomam skaitymui 
 L. Euler „Solutio problematis ad geometriam situs pertinentis“ // „Commentarii academiae scientiarum Petropolitanae“, t. 8, 1741, p. 128–140 

Kategorija:Grafų teorija