Ойлерови цикли и пътища

Ойлеровите цикли и пътища са тясно свързани с обхожданията на графи, като може да се разглеждат както в ориентирани, така и в неориентирани графи. Те са едни от първите възникнали понятия в теорията на графите още през XVIII век от Леонард Ойлер.

Определение: Ойлеров цикъл/път е такъв цикъл/път на графа, при който всяко ребро на графа се среща точно веднъж.

Не всички графи имат Ойлерови цикли и пътища и за това трябва да са изпълнени някои необходими и достатъчни условия. Така например, първият граф има Ойлеров цикъл: $1 - 2 - 3 - 4 - 5 - 2 - 1$. Такива графи се наричат Ойлерови. Това свойство показва, че ако се пробваме да нарисуваме графа с молив, то това може да стане "на един дъх", без да пускаме молива и освен това накрая да се върнем в началото (защото има цикъл). Вторият граф обаче няма Ойлеров цикъл, но има Ойлеров път: $2 - 1 - 2 - 3 - 4 - 5 - 2 - 4$. Тогава казваме, че графът е полу-Ойлеров.

Търсенето на Ойлерови цикли и пътища има най-много смисъл в свързани графи. Ако говорим за неориентирани графи, то това означаваше просто да имаме 1 свързана компонента. Ще разбираме, че ориентиран граф е свързан, ако го разгледаме като неориентиран граф и този граф е свързан.

Има много удобни необходими и достатъчни условия за съществуване на Ойлеров цикъл/път:

• ориентирани графи
• • Един свързан ориентиран граф има Ойлеров цикъл $\iff$ всеки връх има степен равна на $0$ (което означава, че има равен брой влизащи и излизащи ребра). (...може да се докаже, че ориентиран Ойлеров граф освен свързан, винаги е и силно-свързан)
  • Един свързан ориентиран граф има Ойлеров път $\iff$ всеки връх има степен равна на $0$ освен най-много два върха, които имат степени $+1$ и $-1$ (цикълът е и път).
• неориентирани графи
• • Един свързан неориентиран граф има Ойлеров цикъл $\iff$ всеки връх има четна степен.
  • Един свързан неориентиран граф има Ойлеров път $\iff$ всеки връх има четна степен освен най-много два върха, които имат нечетна степен.

Както се вижда от необходимите и достатъчни условия, повечето графи не са Ойлерови. Забележете, че ако има върхове с примки, то тези ребра не пречат на съществуването на Ойлеров цикъл/път, защото в случая на неориентирани графи, ги броим по 2 пъти в степента, а при ориентирани графи се броят веднъж като влизащи и веднъж като излизащ ребра.

Тук ще опишем стандартния алгоритъм, който се ползва - алгоритъмът на Хиерхолзър. Винаги преди да почнем намирането на Ойлеров цикъл/път трябва да проверим дали има такъв с простичките необходими и достатъчни условия. Първо ще говорим за намиране на Ойлеров цикъл в свързан неориентиран Ойлеров граф. Няма значение от кой връх ще почнем да търсим пример за Ойлеров цикъл, защото все пак говорим за цикъл и спокойно можем да го "завъртим", така че да почва от всеки един връх. Единственият проблем с това да намерим директно с DFS Ойлеровия цикъл е, че е възможно по някое време да нямаме накъде да продължим, но да не сме обходили всички ребра. В този момент обаче сме намерили един цикъл, т.е. сме се върнали във върха, от който сме започнали. Нека да видим, че това наистина е така. Това следва лесно от необходимото условие, че в графа всеки връх има четна степен. Наистина, щом сме използвали едно инцидентно ребро с началния връх, то трябва да има още някое (по което можем да се върнем в началния връх) и ако допуснем, че никога няма да го използваме, то може да забележим, че като минаваме през останалите върхове, без последния, използваме по две ребра (едно, с което влизаме в дадения връх и едно, с което го напускаме). Така последния връх трябва да е същият като началния, иначе последният връх няма да има четна степен.

Ако искаме горния алгоритъм да може да състави целия Ойлеров цикъл, то по принцип е възможно да пускаме DFS обхождания по необходените ребра и накрая да сглобим целия цикъл, но това е доста по-сложно и може да направим нещо по умно. Нека за пример на този подход да разгледаме графа вдясно. Възможно е да направим следното обхождане $1 - 2 - 3 - 1$, след което от гледна точка на връх $1$ няма да има необходено ребро, през което да минем. Така за да довършим обхождането трябва да минем и през останалите необходени ребра: $3 - 4 - 5 - 3$ и бихме могли да сглобим Ойлеровия цикъл, като заместим връх $3$ в първото обхождане с втория цикъл и така да намерим следното: $1 - 2 - 3 - 4 - 5 - 3 - 1$.

Алгоритъмът на Хиерхолзър по хитър начин позволява да правим подобно на горното заместване, като правим едно единствено обхождане в дълбочина, но самият цикъл попълваме на излизане от върховете. Нека разгледаме следния псевдокод на така модифицирания DFS:

Очевидно този алгоритъм ще обходи всяко едно ребро на графа, защото графът е свързан. Можем да си мислим, че алгоритъмът работи по следния начин. Както в предния подход, намираме един цикъл (докато все още виждаме необходени ребра от всеки текущ връх), но го попълваме, докато се връщаме назад. Понеже графът е неориентиран, то няма значение в каква ориентация гледаме ребрата. Също така понеже имаме for-цикъл за необходените инцидентни ребра, то когато се връщаме назад и намерим, че някъде все още има необходени ребра, ще се отклоним (от досегашния цикъл), за да ги обходим. Нека предположим, че това се е случило при връх $x$, т.е. този връх е част от досегашния цикъл, но все още има необходено ребро, инцидентно с този връх. Отново можем да видим, че е вярно твърдението от преди, че новото обхождане ще спре, когато завършим цикъл и със сигурност ще сме на връх $x$. Така ще добавим $x$ към Ойлеровия цикъл и ще започнем да добавяме новия намерен цикъл към Ойлеровия, с което правим "заместването" на връх $x$ в стария цикъл с новия цикъл, което преди трябваше да правим ръчно. В крайна сметка по този начин ще обходим всички ребра и междувременно ще сме съставили правилен Ойлеров цикъл.