Oilerio maršrutas

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką
Kiniškas hieroglifas su pažymėtu Oilerio keliu

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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

Išnašos[taisyti | redaguoti kodą]

  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[taisyti | redaguoti kodą]

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


Commons-logo.svg Vikiteka: Oilerio maršrutas – vaizdinė ir garsinė medžiaga

Vikiteka