6. Эйлеровы и гамильтоновы графы. Комбинаторная математика

• Рассматривается обычный неориентированный граф без весов ребер.  

• Задача: обойти все ребра, побывав на каждом ровно один раз, начиная и заканчивая в одной и той же вершине.  

• Если можно обойти все ребра и вернуться в исходную вершину, граф обладает эйлеровым циклом.  

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

• Задача поиска эйлерового пути исторически важна и связана с развитием теории графов.  

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

• Теория графов началась с задачи Эйлера о мостах через Прегель.  

• Эйлер жил в Петербурге и подписывался как русский академик.  

• Теория графов развивалась в России, и Эйлер похоронен в Санкт-Петербурге.  

• Граф с ровно двумя нечетными вершинами обладает эйлеровым путем.  

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

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

• Алгоритм Эйлера: проверить четность вершин и найти путь обхода.  

• Начинать обход с первой вершины и проверять, все ли ребра посещены.  

• Если не все ребра посещены, искать контактную вершину и продолжать обход.  

• Алгоритм Флори: строит эйлеров цикл за один проход.  

• Удаляет дубликаты ребер и выбирает ребро, которое не является мостом в оставшемся графе.  

• Презентация сделана для удобства и повторения материала.  

• Пример обхода графа: выбор ребер, чтобы не создавать мосты.  

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

• Алгоритм Флюри строит полный цикл за один проход.  

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

• Алгоритм Флюри не добавляет новые ребра, а только удаляет старые.  

• Эйлеровы графы имеют четную степень вершин.  

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

• Алгоритмы для эйлеровых и нейлеровых графов работают одинаково.  

• Задача поиска гамильтонова цикла NP-полная.  

• Гамильтоновы графы требуют посещения каждой вершины ровно один раз.  

• В отличие от эйлеровых графов, гамильтоновы графы не обязательно обходить все ребра.  

• Задача минимизации веса пути.  

• Гамильтоновы графы: можно ли обойти все вершины?  

• Теоремы о гамильтоновых графах: степени вершин и количество ребер.  

• Полный граф: можно обойти все вершины.  

• Граф типа "колесо": степени вершин равны 2, но граф гамильтонов.  

• Теоремы работают в одну сторону, но есть обобщения.  

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

• Примеры графов, где условия не выполняются.  

• Задача о молочнике: найти минимальный путь для развоза молока.  

• Решение задачи: перебор перестановок вершин.  

• Проблемы с перебором: множество ненужных перестановок.  

• Метод перебора всех возможных путей.  

• Проблемы с тупиками и повторными посещениями вершин.  

• Построение дерева возможных обходов.  

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

• Пример: из двойки можно пойти в тройку или четверку, из тройки можно пойти в двойку или четверку, и так далее.  

• Важно найти путь с минимальным расстоянием.  

• Жадный алгоритм выбирает самый короткий путь, но не всегда оптимально.  

• Пример: из вершины 1 можно пойти в 3, 4, 6, но это не всегда оптимально.  

• Жадный алгоритм может не привести к решению даже для небольшого количества вершин.  

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

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

• Применяется для решения различных задач, включая обработку изображений и анализ текстов.  

• Матрица смежности графа заполняется бесконечностью для несуществующих ребер.  

• В каждой строке и столбце находится минимальный элемент, который вычитается для получения нулей.  

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

• Вычисляется граница для гамильтонова цикла, которая не может быть меньше определенного значения.  

• Для каждого нулевого элемента считается штраф, который является суммой нулей и одного.  

• Выбирается элемент с максимальным штрафом, и строится дерево решений.  

• Удаление ребер, исходящих из вершины 4 и входящих в вершину 5.  

• Создание нового ориентированного графа и несимметричной матрицы.  

• Удаление ребер, которые больше не используются.  

• Повторение процесса для нового графа и матрицы.  

• Вычисление новой границы и добавление её к старой границе.  

• Выбор элементов с максимальным штрафом и повторение процесса.  

• Исследование минимального пути и отбрасывание ненужных ветвей.  

• Метод ветвей и границ позволяет оптимизировать перебор.  

• В худшем случае метод может быть неэффективным, но чаще всего быстрее.  

• Метод ветвей и границ не является панацеей, но имеет право на жизнь.  

• В худшем случае сложность метода может быть высокой.  

• Метод позволяет быстрее решать задачи, но не всегда.  

• Метод рассматривает только ребра, которые уже исследованы.  

• Если все ребра бесконечны, это означает тупик и отбрасывание ветви.  

• Задача о 57 городах Европы до сих пор не решена полностью.  

• Метод может быть применен для решения задач в Татарстане и других регионах.  

• В Татарстане задача решается для населенных пунктов, но не для крупных городов.  

• В Европе задача о 57 городах остается нерешенной, несмотря на использование различных методов.