Эйлеровы пути и циклы

Определение. Эйлеров путь — это путь в графе, проходящий через все его рёбра.

Определение. Эйлеров цикл — это эйлеров путь, являющийся циклом.

Для простоты будем считать, что граф неориентированный.

Также есть понятие гамильтонова пути и цикла.

Чтобы проверить, существует ли эйлеров путь, нужно воспользоваться следующей теоремой.

Пусть дан неориентированный связный цикл. Эйлеров цикл существует тогда и только тогда, когда степени всех вершин чётны. Эйлеров путь существует тогда и только тогда, когда количество вершин с нечётными степенями равно двум (или нулю, в случае существования эйлерова цикла).

Кстати, аналогичная теорема есть и для ориентированного графа (можете сами попытаться сформулировать).

Доказать это можно например через лемму о рукопожатиях.

Как теперь мы будем решать задачу нахождения цикла в предположении, что он точно есть. Давайте запустимся из произвольной вершины, пройдем по любому ребру и удалим его.

void euler(int v){
    stack >s;
    s.push({v, -1});
    while (!s.empty()) {
        v = s.top().first;
        int x = s.top().second;
        for (int i = 0; i < g[v].size(); i++){
            pair e = g[v][i];
            if(!u[e.second]){
                u[e.second]=1;
                s.push(e);
                break;
            }
        }
        if (v == s.top().first) {
            if (~x) {
                p.push_back(x);
            }
            s.pop();
        }
    }
}

Упражнение. Сформулируйте и докажите аналогичные утверждения для случая ориентированного графа.