Ојлеров пут

Из Википедије, слободне енциклопедије

Ојлеров пут је пут у неусмереном графу који кроз сваку ивицу пролази тачно једном. Ако такав пут постоји у графу, он се назива траверзибилан. Први га је описао Леонард Ојлер, који је решавао чувени проблем Седам мостова Конинсберга 1736.

Особине[уреди]

  • Повезани неусмерени граф је Ојлеров ако сваки чвор тог графа има паран степен.
  • Усмерени граф је Ојлеров ако је повезан и ако је за сваки чвор број ивица који полазе из њега и завршавају се у њему једнак.
  • Неусмерен граф је траверзибилан ако је повезан и ако највише два чвора имају непаран степен.

Опис алгоритма[уреди]

Уочимо граф чије ивице припадају истој компоненти и чија највише два чвора имају непаран степен. Крећемо од оног чвора који има непаран степен; ако такав чвор не постоји, онда можемо изабрати произвољан чвор. У сваком кораку крећемо се кроз ону ивицу чије избацивање не би утицало на поделу графа на више компонената (осим ако немамо другог избора), а затим ту ивицу обришемо. На крају су у низу садржане оне ивице које се налазе на Ојлеровом путу. (Ако су сви чворови били парног степена вратићемо се у почетни чвор, што не важи за случај кад су два чвора непарног степена.)

Спољашње везе[уреди]

Викиостава
Викимедијина остава има још мултимедијалних датотека везаних за: Ојлеров пут