#algorithm #math #graph-theory
#Алгоритм #Математика #Теория графов
Вопрос:
Недавно мне поставили задачу нарисовать дом с крестиком посередине, не поднимая ручки и не проводя никаких линий. Ссылка на проблему
Приведенная выше ссылка начинает погружаться в некоторые теории графов, связанные с проблемой, однако нет упоминания о том, как можно решить эту проблему с помощью алгоритмов теории графов.
Какие алгоритмы можно было бы использовать здесь, и каков был бы правильный способ сформулировать эту проблему с использованием языка теории графов?
Комментарии:
1. Два конкретных алгоритма построения эйлерова пути упоминаются в статье Википедии об эйлеровых путях en.wikipedia.org/wiki / … — обратите внимание, что алгоритм, который находит только цикл Эйлера, может также найти след Эйлера, дополняя граф другим ребром, которое соединяет 2 вершины, имеющие нечетную степень, затем удаляя это ребро изрешение найдено.
2. @moreON спасибо за быстрый ответ! Если вы хотите отправить этот ответ в качестве ответа, я с радостью приму его.
Ответ №1:
Два конкретных алгоритма построения эйлерова пути упоминаются в статье Википедии об эйлеровых путях. Это алгоритм Флери и алгоритм Иерхольцера.
Обратите внимание, что алгоритм, который находит только цикл Эйлера, может также найти след Эйлера, добавив в граф другое ребро, которое соединяет 2 вершины, имеющие нечетную степень, затем повернув решение так, чтобы добавленное ребро было первым или последним, затем удалив это ребро из найденного решения.