Что такое эйлеровы графы: определение термина
Граф — это модель из вершин и ребер, где вершины можно представлять как точки, а ребра как линии между ними. Эйлеровым называют граф, в котором существует эйлеров путь или эйлеров цикл.
Эйлеров путь — это маршрут, который проходит по каждому ребру ровно один раз. Эйлеров цикл — то же самое, но маршрут заканчивается там же, где начался.
Если граф связный и у всех вершин степень четная, то в нем существует эйлеров цикл. А когда две вершины имеют нечетную степень, то существует эйлеров путь, но цикл уже невозможен.
Зачем нужны эйлеровы графы
Они помогают решать задачи на маршруты: как пройти по всем дорогам, коридорам или участкам сети, не проходя одно и то же ребро дважды. Это удобно, когда повторение пути означает лишние затраты времени или ресурсов.
На основе идей эйлеровых графов рассматривают задачи про обход улиц, прокладку маршрутов обслуживания, проверку сетей и планирование обходов. Даже если реальная задача сложнее, признак эйлерового пути часто дает быстрый ответ, возможен ли идеальный маршрут без повторов.
