Как построить эйлеров цикл/цепь в графе

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

• Эйлеров цикл завершается в той же вершине, из которой начался.  

• Эйлерова цепь завершается в другой вершине.  

• Задача: нарисовать домик, не проходя по линии дважды.  

• Проблема: застревание в узловых точках.  

• Решение: убедиться, что из каждой узловой точки есть выход.  

• Эйлерова цепь строится, если есть две вершины нечетной степени.  

• Пример: домик с двумя угловыми вершинами.  

• Построение маршрута: стартовая вершина, обход всех вершин, возвращение в стартовую вершину.  

• Эйлеров цикл существует, если все вершины имеют четную степень.  

• Пример: домик с четной степенью вершин.  

• Построение цикла: стартовая вершина, обход всех вершин, возвращение в стартовую вершину.  

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

• Пример: обход графа с учетом увеличения числа компонент связанности.  

• Программная реализация: не следить за увеличением числа компонент связанности.  

• Пример: обход графа без учета увеличения числа компонент связанности.  

• Регулярный граф: все вершины имеют одинаковую степень.  

• Построение эйлерова цикла: начать с любой вершины, следить за увеличением числа компонент связанности.  

• Пример: обход графа с учетом увеличения числа компонент связанности.  

• Рассматривается возможность нарисовать картинку одной линией, не отрывая ручку от бумаги.  

• Переформулируется задача: является ли данный граф эйлеровым?  

• Определяются узлы и их степени.  

• Подсчитываются степени вершин.  

• Некоторые вершины имеют степень два, другие - три и четыре.  

• Демонстрируется, что можно пройти по всем линиям, не повторяясь.  

• Определяется начальная вершина для маршрута.  

• Проверяется, как маршрут проходит через развилки и треугольники.  

• Маршрут заканчивается в вершине с четвертой степенью.  

• Задача Эйлера родилась в Кенигсберге.  

• Эйлер изучал возможность пройти по всем мостам и вернуться домой.  

• Построена математическая модель, показывающая, что это невозможно.  

• Обозначаются берега буквами, а мосты - ребрами.  

• Рассматриваются вершины степени три и пять.  

• Для решения задачи нужно добавить еще несколько мостов.  

• Один из мостов Калининграда был достроен для решения задачи.  

• Правитель построил еще один мост, сделав две вершины четными.  

• Маршрут можно начать и закончить на острове Канта.