Условие
Граф состоит из треугольников ABC и ADE с общей вершиной A. Найдите замкнутый маршрут, который проходит каждое ребро ровно один раз.
Решение по шагам
Степень A равна 4, степени B,C,D,E равны 2. Граф связен и все степени чётные, поэтому существует эйлеров цикл. Один маршрут: A→B→C→A→D→E→A.
Он последовательно проходит первый треугольник, возвращается в точку соединения, проходит второй и заканчивается в A. Вершина A повторяется, но это разрешено: условие ограничивает повторение рёбер, а не вершин.
Проверка результата
Шесть переходов используют рёбра AB,BC,CA,AD,DE,EA без повторений. Начальная и конечная вершины совпадают.
Типичная ошибка
Эйлеров цикл не следует путать с гамильтоновым, где нужно посетить каждую вершину ровно один раз. Общая вершина двух треугольников как раз делает различие заметным.
Что даёт этот метод
Для связного неориентированного графа эйлеров цикл существует при чётности всех степеней. При двух нечётных вершинах возможен незамкнутый эйлеров путь между ними.
Дальше по теме
Комбинаторика и дискретная математика: другие задачи и разборы.
Учебное условие и объяснение сформулированы редакцией damirock.com. Это самостоятельный разбор, а не официальный билет или ключ экзамена. Числа относятся к модели задачи.