Информатика · объяснение и практика
Как степени вершин и связность проверяют обход каждого ребра
Проверьте эйлеров обход неориентированного графа: посчитайте нечётные степени, найдите компоненту всех рёбер и не перепутайте маршрут с посещением вершин.

В теме Графы и маршруты · Учебная карта
Главная мысль
Эйлеров маршрут проходит каждое ребро ровно один раз; вершины при этом могут повторяться. Для конечного неориентированного графа с хотя бы одним ребром все вершины ненулевой степени должны быть связаны. Замкнутый обход требует чётных степеней, незамкнутый — ровно двух нечётных концов.
Вход и выход расходуют рёбра парами
Если маршрут пришёл в промежуточную вершину, он должен затем выйти по другому ещё не использованному ребру. Такие посещения образуют пары входа и выхода. Поэтому у промежуточных вершин степень чётная. Начало и конец незамкнутого маршрута могут иметь по одному непарному ребру; отсюда появляются именно две нечётные вершины, а не произвольное количество.
Представим цепочку из рёбер А—Б, Б—В и В—Г. Степени равны одному, двум, двум и одному. Маршрут А, Б, В, Г использует все рёбра один раз и заканчивается в другой вершине. Добавление Г—А превращает цепочку в квадрат с чётными степенями и допускает возвращение в исходную точку.
Чётность не заменяет связность
Два отдельных треугольника имеют только чётные степени, но общий маршрут по всем шести рёбрам невозможен: между частями нет перехода. Поэтому сначала выделяют вершины, участвующие в рёбрах, и проверяют их связность. Один изолированный узел рядом с квадратом не мешает обходу рёбер квадрата, если задача не требует отдельно посетить этот узел.
При нескольких рёбрах между одной парой каждое считается отдельным объектом обхода. Петля добавляет к степени два, потому что оба её конца находятся в одной вершине. Полезно нумеровать рёбра, а не проверять только последовательность названий вершин: иначе параллельные связи легко спутать и незаметно пройти одну дважды.
Пример
Треугольник соединён одним дополнительным ребром с новой вершиной. Возможен ли обход всех четырёх рёбер?
У новой вершины степень один, у точки присоединения три, у остальных две. Нечётных вершин ровно две, граф связен. Можно начать в новой вершине, войти в треугольник и пройти его до возвращения к точке присоединения.
Запишите, что именно проверяет критерий
Для неориентированного графа связность рёбер вместе с указанной чётностью не только необходима, но и достаточна. Чтобы получить сам маршрут, можно последовательно строить обходы и соединять их в общих вершинах. Однако произвольный жадный выбор очередной связи способен раньше времени завести в тупик, поэтому критерий существования не заменяет корректный алгоритм построения.
В ориентированном графе отдельно учитывают входящие и исходящие степени и условия связности; переносить туда школьное правило «ноль или две нечётные» нельзя. Граф без рёбер также требует соглашения о пустом маршруте. Сначала уточните тип графа и цель обхода, затем применяйте проверку. Если нужно посетить каждую вершину один раз, это уже гамильтонова задача.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли повторно попасть в уже посещённую вершину?
Да. Запрет относится к повторному использованию ребра. Через одну вершину эйлеров маршрут может проходить несколько раз.
Почему четыре нечётные вершины не подходят?
Незамкнутый маршрут имеет только два конца. Остальные посещения должны распадаться на пары входа и выхода, поэтому ещё две нечётные вершины оставить некуда.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему путь через все вершины не равен пути через все рёбра
Сравните обход вершин и обход рёбер на двух небольших графах: выясните, почему знакомая проверка чётности не решает гамильтонову задачу.
Открыть темуКогда список смежности выгоднее матрицы
Сравниваем список смежности и матрицу по памяти и операциям, сохраняем направление и вес рёбер и выбираем структуру под разреженность и требуемые запросы.
Открыть тему