Ојлерови и полуојлерови мултиграфови

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

Седам кенингсбершких мостова

Ојлер је 1741. године објавио научни рад о 7 кенингсбершких мостова, који се сматра и привим радом из теорије графова.
Проблем може бити формулисан математички:
С обзиром на граф на слици, да ли је могуће да се изгради пут (или циклус, то је пут који почиње и завршава се у једном истом чвору), који посети сваку грану тачно једном?
Ојлер је проблем решио тако што је конструисао припадни мултиграф чији чворови одговарају обалама реке и речним острвима, а гране мостовима. Два чвора мултиграфа спојена су са онолико грана колико мостова спаја одговарајуће делове града. Тај мултиграф илустрован је на слици 2.

Битне теореме

Теорема 1(Ојлерова теорема)

Нетривијалан повезан мултиграф је Ојлеров ако и само ако су сви чворови тог мултиграфа парни.

Теорема 2

Нетривијалан повезан мултиграф је полуојлеров ако и само ако садржи 0 или 2 чвора непарног степена.

Флеријев алгоритам

Флеријев алгоритам је алгоритам који прихвата Ојлеров мултиграф, а враћа једну Ојлерову стазу тог графа.
У следећој табели је приказан поступак како алгоритам функционише:

Кључ	Опис корака
K1	Изабрати произвољан чвор v0, w=v0 (ако тражимо Ојлеров пут, v0 мора бити један од два чвора непарног степена).
K2	Стаза w=v0 e1 v1 e2 ... ei vi. Наредну грану ei+1 одабрати из E∖{e1,...,ei} тако да је инцидентна са vi и при томе није мост графа Gi=G−{e1,...,ei} осим ако нема друге могућности.
K3	КРАЈ када корак K2 не може да се извршава.

Напомена: Кључно правило: "не прелази мост осим ако мораш".

Закључак

Ојлерови и полуојлерови мултиграфови, као и Флеријев алгоритам, имају значајну примену у практичним проблемима теорије графова.