%\author{Савон Юлия}
%\date{26 ноября 2015}
\Section{Эйлеровые графы, циклы и сопутствующие алгоритмы}{13 ноября}{Савон Юлия}

{\bf Def 1:} Эйлеров цикл - цикл по всем рёбрам графа
{\bf Def 2:} Эйлеров путь - путь по всем рёбрам графа

{\it Критерии наличия эйлерова пути:} 

s, t - вершины ориентированного графа

1)$deg_{in}(t) - deg_{out}(t) = 1$

$deg_{out}(t) - deg_{in}(s) = 1$

$\forall x$(x - оставшиеся вершины графа) $deg_{out}(x) - deg_{in}(x) = 0$

2)Связность графа

{\it Док-во:} 1) Из s в t можно пройти.(если мы вошли в какую-то вершину, то из неё мы можем выти, возможно за исключением случая вершины t, но бесконечного пути быть не может, значит он закончится в t)

2)Возьмем максимальный путь и скажем, что он эйлеров(От противного, пусть нет, тогда т.к. граф связен, то в одну из вершин не взятых в путь есть входящие и сходящие рёбра, но теперь т.к. у всех вершин $deg_{out}(x) - deg_{in}(x) = 0$, то идя по невзятым рёбрам мы вернемся в данную вершину, а значит сможем увеличить путь).

{\it Алгоритм поиска:}

\lstinputlisting{savon/search_way.cpp} 

{\it Что же делать, если граф неориентированный?}

1)Заметим, что он останется связным.

2) Запоминаем номера одинаковых рёбер.

3)При необходимости лениво удаляем.

\pagebreak

\Subsection{ Задача(De Brujiu sequence): } 

Имеется Алфавит, все слова которого сроки длины n, состоящие из 0 и 1. Существует ли строка содержащая все возможные слова как подстроки.

{\it Решение:} 

Ответ: Содержит.

Почему: 

\begin{proof}

1)Рассмотрим граф, в котором вершины - это все возможные подстроки длины $n - 1$, пусть из вершины в вершину есть рёбро, если одна является префиксом слова, а другая суффиксом. 

2)Заметим, что из каждой вершины выходит 2 ребра и в каждую входит. Кроме того граф связен, т.к. можно за n действий всегда превратить одну строку в другую. 

3)начит у нас существует эйлеров путь по всем рёбрам(Считаем началом  концом одну и ту же вершину, можно разделить мысленно на 2, из одной будет исходить 2 ребра в входить одно, а во вторую будет входить оставшееся). В графе $2^{n - 1}$ вершинб из каждой выходит 2 ребра. 

4)Всего рёбер $2^{n}$. Заметим, что каждое ребро задает строку длины n. Это значит, что наши рёбра это ровно $2^{n}$ слов алфавита т.к. префикс и суффикс в паре уникальны. 

{\it Итого:} Pаписав начальную вершину и при переходе записывая соответствующий новую цифру мы получим нашу строку длины $(n - 1) + 2^{n}$.

\end{proof}