Задача: Эйлеров путь в графе
Задача: Эйлеров путь в графе Условие задачи: Можно ли нарисовать фигуру, не отрывая карандаша от бумаги и не проводя по одной линии дважды? Или — можно ли пройти по всем рёбрам графа ровно один раз? Это классическая задача на эйлеров путь. ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Пример графа Рассмотрим простой граф: A --- B | / | | / | C --- D Рёбра: AB, AC, BC, BD, CD ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Решение 1. Определим степени вершин (количество выходящих рёбер): | Вершина | Степень | | ------- | ------- | | A | 2 | | B | 3 | | C | 3 | | D | 2 | 2. Критерий существования эйлерова пути - Эйлеров путь существует, если связный граф содержит ровно две вершины нечётной степени (начало и конец маршрута), а остальные — чётной. - Если все вершины чётной степени — есть эйлеров цикл (можно начать и закончить в одной точке). В нашем примере: - Нечётные степени у B и C; - Чётные — у A и D. Значит, эйлеров путь существует. Начать нужно в одной из нечётных вершин (B или C), закончить — в другой. 3. Пример прохождения Один из возможных маршрутов: 𝐵→𝐴→𝐶→𝐵→𝐷→𝐶 Проверяем: каждое ребро пройдено ровно один раз, карандаш не отрывался. ⎯⎯⎯⎯⎯⎯⎯⎯⎯⎯ Вывод Задача о прохождении по каждому ребру графа ровно один раз решается с помощью анализа степеней вершин. Такой маршрут называется эйлеровым путём. Если бы все вершины были чётной степени, существовал бы эйлеров цикл (замкнутый маршрут). Если более двух нечётных — такой путь невозможен. Этот принцип применяется в задачах инспекции дорог, трассировки печатных плат, головоломках типа "нарисуй, не отрывая руки" и других практических ситуациях!