Oilerio maršrutas

(Nukreipta iš puslapio Oilerio kelias)

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 redaguoti

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 redaguoti

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:[1][2]

{ 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.[2]

Taikymai redaguoti

Oilerio maršrutai naudojami bioinformatikoje DNR sekai atkurti iš jos fragmentų.[3]

Išnašos redaguoti

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

Papildomam skaitymui redaguoti

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