Обратите внимание на другие наши ресурсы: Youtube | Telegram | VK | Rutube | Dzen | Boosty

Определение

Эйлеров цикл - замкнутый путь, проходящий через каждое ребро графа ровно по одному разу.

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

---

Принцип работы алгоритма

1. Выбрать произвольную вершину.

2. Выбрать произвольное ребро R, которое связано с текущей вершиной.

3. Назначить текущей вершиной вторую вершину ребра R.

4. Удалить ребро R из графа и записать в результат.

   Если степень текущей вершины больше 1, то нельзя выбирать ребро, которое при удалении увеличит число компонент связности. Т. е. нельзя выбирать ребро, которое при удалении разделит исходный граф на несколько независимых графов.

5. Если в графе ещё остались рёбра перейти на шаг 2.

---

Пример работы

Текущий цикл: 1

1. Выберем вершину 1

2. Выберем ребро 1-3

3. Новой вершиной становится вершина 3

Текущий цикл: 1 -> 3

1. Удаляем ребро 1-3

2. Выберем ребро 3-4

3. Новой вершиной становится вершина 4

Текущий цикл: 1 -> 3 -> 4

1. Удаляем ребро 3-4

2. Выберем ребро 4-6

3. Новой вершиной становится вершина 6

Текущий цикл: 1 -> 3 -> 4 -> 6

1. Удаляем ребро 4-6

2. Выберем ребро 6-8

3. Новой вершиной становится вершина 8

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8

1. Удаляем ребро 6-8

2. Выберем ребро 8-10

3. Новой вершиной становится вершина 10

### **Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10**

1. Удаляем ребро 8-10

2. Выберем ребро 10-11

3. Новой вершиной становится вершина 11

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11

1. Удаляем ребро 10-11

2. Выберем ребро 11-9

3. Новой вершиной становится вершина 9

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9

1. Удаляем ребро 11-9, из вершины 11 больше нет путей в другие вершины, поэтому вершина 11 тоже удаляется

2. Выберем ребро 9-10

3. Новой вершиной становится вершина 10

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10

1. Удаляем ребро 9-10

2. Выберем ребро 10-2

3. Новой вершиной становится вершина 2

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2

1. Удаляем ребро 10-2

2. Выберем ребро 2-3

3. Новой вершиной становится вершина 3

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3

1. Удаляем ребро 2-3

2. Выберем ребро 3-9

3. Новой вершиной становится вершина 9

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9

1. Удаляем ребро 3-9, из вершины 3 больше нет путей в другие вершины, поэтому вершина 3 тоже удаляется

2. Выберем ребро 9-7

3. Новой вершиной становится вершина 7

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7

1. Удаляем ребро 9-7, из вершины 9 больше нет путей в другие вершины, поэтому вершина 9 тоже удаляется

2. Выберем ребро 7-6

3. Новой вершиной становится вершина 6

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6

1. Удаляем ребро 7-6

2. Выберем ребро 6-5

3. Новой вершиной становится вершина 5

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5

1. Удаляем ребро 6-5, из вершины 6 больше нет путей в другие вершины, поэтому вершина 6 тоже удаляется

2. Выберем ребро 5-4

3. Новой вершиной становится вершина 4

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5 -> 4

1. Удаляем ребро 5-4

2. Выберем ребро 4-7

3. Новой вершиной становится вершина 7

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5 -> 4 -> 7

1. Удаляем ребро 4-7, из вершины 4 больше нет путей в другие вершины, поэтому вершина 4 тоже удаляется

2. Выберем ребро 7-8

3. Новой вершиной становится вершина 8

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5 -> 4 -> 7 -> 8

1. Удаляем ребро 7-8, из вершины 7 больше нет путей в другие вершины, поэтому вершина 7 тоже удаляется

2. Выберем ребро 8-5

3. Новой вершиной становится вершина 5

Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5 -> 4 -> 7 -> 8 -> 5

1. Удаляем ребро 8-5, из вершины 8 больше нет путей в другие вершины, поэтому вершина 8 тоже удаляется

2. Выберем ребро 5-2

3. Новой вершиной становится вершина 2

**Текущий цикл: 1 -> 3 -> 4 -> 6 -> 8 -> 10 -> 11 -> 9 -> 10 -> 2 -> 3 -> 9 -> 7 -> 6 -> 5 -> 4 -> 7 -> 8 -> 5 -> 2 -> 1

1. Удаляем ребро 5-2, из вершины5 больше нет путей в другие вершины, поэтому вершина 5 тоже удаляется

2. Выберем ребро 2-1

3. Новой вершиной становится вершина 1

После удаления ребра 2-1, свободных рёбер в графе не останется, следовательно алгоритм прекратил своё действие, потому что прошёл по всем рёбрам графам ровно один раз.

Вычислительная сложность

Сложность алгоритма: $O(|V| + |E|)$, где V - количество вершин, а E - количество рёбер

---

Псевдокод

Аннотация:
graph - граф  
start - стартовая вершина  
v - вершина графа
stack - стек
start - начальная вершина
result - массив результата
curr_node - текущий узел
next_node - следующий узел
----------------------------------------------------------------------------------------
  
Функция Проверки чётности вершин(graph)  
    для каждой вершины v графа 
    
        если из v выходит нечётное количество рёбер 
                проверка провалена  
                
    проверка пройдена  
  
  
Функция поиска цикла эйлера(graph, start)
    если Проверка чётности вершин провалена  
        то эйлерова цикла в графе нет
           возвращаем -1        
        
    stack
    stack.push(start)
    
    result
    
    пока stack не пустой  
        curr_node <- stack.front()   
      
        если у curr_node есть непосещённые соседи  
            next_node
            удаляем ребро curr_node--next_node  
            удаляем ребро next_node--curr_node  
             
            в stack добавляем next_node 

            обновляем result
            
        иначе если все соседи curr_node были посещены  
            stack.pop()

---

Реализация на Python

Аннотация:
check_node_power - функция проверки степени вершин
graph - матрица смежности, в которой хранится граф
vertex - вершина графа
euler_cycle - эйлеров цикл
start_vertex - начальная вершина
cycle - массив результата цикла
stack - стек
current_vertex - текущая вершина
next_vertex - следующая вершина
----------------------------------------------------------------------------------------

def check_node_power(graph):  
    for vertex in graph:  
        if len(graph[vertex]) % 2 != 0:  
            return False  
    return True  
  

def euler_cycle(graph, start_vertex):  
    if not check_node_power(graph):  
        return -1  
  
    cycle = []  
    stack = [start_vertex]  

    while stack:  
        current_vertex = stack[-1]  
        if len(graph[current_vertex]) > 0:  
            next_vertex = graph[current_vertex].pop()  
            graph[next_vertex].remove(current_vertex)  
            stack.append(next_vertex)  
            cycle = list(stack)  
  
        else:    
            stack.pop()  

    if cycle[len(cycle) - 1] != start_vertex:  
        cycle.append(start_vertex)  

    return cycle

---

Олимпиадная реализация на C++

Аннотация:
typedef - переопределение имени типа данных
graph - матрица смежности, в которой хранится граф
v - вершина графа
s - начальная вершина
res - массив результата цикла
stack - стек
curr - текущая вершина
next - следующая вершина
----------------------------------------------------------------------------------------

typedef vector<int> vi;
typedef unordered_map<int, vector<int>> mivi;
typedef pair<int, vector<int>> ivi;
bool check(mivi graph) {
    for (ivi v : graph) {
        if (v.second.size() % 2 != 0)
            return 0;
    }
    return 1;
}
vi euler_cycle(mivi & graph, int s) {
    if (!check(graph))
        return vi { -1 };
    vi res;
    res.push_back(s);
    vector<int> stack;
    stack.push_back(s);
    
    while (!stack.empty()) {
        int curr = stack.back();
        if (graph[curr].size() > 0) {
            int next = graph[curr].back();
            graph[curr].pop_back();
            graph[next].erase(
                remove(graph[next].begin(),
                       graph[next].end(), curr),
                graph[next].end()
            );
            stack.push_back(next);
            res = stack;
        }
        else
            stack.pop_back();
    }
    if (res.back() != s)
        res.push_back(s);
    return res;
}

---

Продуктовая реализация на C++

Аннотация:
check_node_power - функция проверки степени вершин
graph - матрица смежности, в которой хранится граф
vertex - вершина графа
euler_cycle - эйлеров цикл
start_vertex - начальная вершина
cycle - массив результата цикла
stack - стек
current_vertex - текущая вершина
next_vertex - следующая вершина
----------------------------------------------------------------------------------------

bool check_node_power(std::unordered_map<int, std::vector<int>> graph) {
    for (std::pair<int, std::vector<int>> vertex : graph) {
        if (vertex.second.size() % 2 != 0)
            return false;
    }
    return true;
}

std::vector<int> euler_cycle(std::unordered_map<int, std::vector<int>> &graph, int start_vertex) {

    if (!check_node_power(graph))
        return std::vector<int> { -1 };

    std::vector<int> cycle;
    std::vector<int> stack;
    stack.push_back(start_vertex);

    while (!stack.empty()) {
        int current_vertex = stack.back();
        if (graph[current_vertex].size() > 0) {
            int next_vertex = graph[current_vertex].back();
            graph[current_vertex].pop_back();
            graph[next_vertex].erase(
                std::remove(graph[next_vertex].begin(), 
                            graph[next_vertex].end(), 
                            current_vertex), 
                graph[next_vertex].end()
            );
            stack.push_back(next_vertex);

            cycle = stack;
        }

        else
            stack.pop_back();
    }

    if (cycle.back() != start_vertex) 
        cycle.push_back(start_vertex);
    return cycle;
}