Ојлеров циклус

Да се одреди дали еден граф има Ојлеров пат или циклус е лесно, се применуваат две правила.

• Граф има Ојлеров циклус ако и само ако е поврзан (кога ќе ги извадиме сите темиња со степен 0) и секое теме има "парен степен".
• Граф има Ојлеров пат ако и само ако е поврзан и сите темиња освен две имаат парни степени
• Во вториот случај, едно од двете темиња кое има непарен степен мора да биде почетно теме, додека другото е крајното теме.

Основната идеја на алгоритмот е да се почне од некое теме во графот и да се одреди цуклус кој се враќа пак во истото теме. Сега, кога е додаден циклус (во спротивен редослед), алгоритмот гарантира дека сите ребра на сите темиња по тој пат се искористени. Ако постои некое теме по должината на тој пат што има ребро кое што не е искористено, тогаш алгоритмот наоѓа циклус што почнува во тоа теме што го користи тоа ребро и го вметнува тој циклус во моменталнио. Ова продолжува се додека сите ребра на сите темиња во оригиналниот циклус се искористени, па резултантниот циклус е Ојлеров.

Да поедноставиме, за да се одреди Ојлеров циклус на граф, одбираме почетно теме и вршиме рекурзија. На секој рекурзивен чекор:

• Ако темето нема соседи, тогаш го додаваме темето на циклусот и се враќаме
• Ако темето има соседи, тогаш правиме листа на сите соседи и нив ги обработуваме (што вклучува нивно бришење од листата на темиња на кои треба да работиме) додека темето нема повеќе соседи
• За да процесираме теме, го бришеме реброто помеѓу моменталното теме и неговиот сосед, вршиме рекурзија на соседот, и го додаваме моменталното теме на циклусот

Овој алгоритам работи во O(m + n) време, каде m е бројот на ребра и n е бројот на темиња, ако се чува графот во "листа на соседи".

Литература: USACO