Одним росчерком
Нечётные вершины
Проведено рёбер
Способов обвести

    • 0 нечётных вершин: цикл, из любой вершины обратно в неё
    • 2 нечётные вершины: путь из одной в другую
    • 4 и больше: одним росчерком невозможно

    Метод

    Подробнее об эйлеровых путях и циклах

    Поиск эйлеровых путей

    Можно ли нарисовать домик Деда Мороза, не отрывая карандаша и не проводя ни одну линию дважды? Можно, но только начав с одного из двух нижних углов, и из каждого есть 44 способа. Дело в степени вершины — числе линий, сходящихся в ней: всякий раз, проходя через вершину, карандаш расходует две её линии. Леонард Эйлер нашёл это правило в 1736 году на семи мостах Кёнигсберга. Обведите фигуру сами, посмотрите, где и почему вы застреваете, попросите подсказку или посмотрите, как её рисует алгоритм. Выберите фигуру и обведите её: коснитесь вершины, чтобы начать, затем по порядку касайтесь рёбер или следующих вершин либо ведите пальцем от вершины к вершине. Каждое ребро проходится только один раз. Назад отменяет шаг, Подсказка показывает следующее безопасное ребро, а Решить проигрывает по шагам алгоритм Флёри или Хирхольцера. Нечётные вершины закрашены, а значок у каждой вершины — её степень. В режиме Рисовать касание пустого места добавляет вершину, касание двух вершин соединяет их, ещё одно добавляет второе ребро; перетащите вершину, чтобы передвинуть её. Стереть убирает вершины и рёбра. Если нечётных вершин больше двух, Добавить вставляет рёбра, после которых фигуру можно обвести.

    Как это работает

    1. Выберите фигуру — например, семь мостов Кёнигсберга, домик Деда Мороза или звезду, — либо нарисуйте свою в режиме Рисовать, с любым числом рёбер между двумя вершинами.
    2. Коснитесь вершины, чтобы начать, затем по порядку касайтесь рёбер или вершин либо ведите пальцем от вершины к вершине. Если застрянете, строка состояния объяснит почему; Назад отменяет шаг, а Подсказка показывает безопасное ребро.
    3. Прочтите правило степеней под фигурой, добавьте к невозможной фигуре предложенные рёбра или нажмите Решить и посмотрите, как алгоритм Флёри или Хирхольцера рисует её по шагам.

    Почему всё решают нечётные вершины

    Росчерк, проходящий через вершину, приходит по одной линии и уходит по другой, то есть расходует линии этой вершины парами. Линия может остаться без пары только там, где росчерк начинается или заканчивается. Поэтому вершина с нечётным числом линий обязана быть началом или концом. Если нечётных вершин нет, росчерк заканчивается там, где начался: это эйлеров цикл. Если их две, он идёт из одной в другую: это эйлеров путь. Если четыре и больше, концов слишком много для одного росчерка, и k нечётных вершин требуют k/2 росчерков. В Кёнигсберге было четыре участка суши с пятью, тремя, тремя и тремя мостами: все четыре нечётные, поэтому ни одна прогулка не могла пройти по каждому мосту один раз. Один новый мост между двумя из них сделал бы прогулку возможной.

    Алгоритмы Флёри и Хирхольцера

    Знать, что фигуру можно нарисовать, — не то же самое, что нарисовать её: неосторожный росчерк может отрезать себя от линий, которые ему ещё нужны. Алгоритм Флёри 1883 года избегает этого одним правилом: никогда не идите по мосту, то есть по линии, удаление которой разделило бы оставшиеся линии на две части, если только другой линии нет. Алгоритм Хирхольцера из статьи, опубликованной в 1873 году, быстрее: идите куда угодно, пока не застрянете, а это возможно только в начальной точке; затем из вершины маршрута, у которой ещё есть свободные линии, пройдите ещё один замкнутый круг и вставьте его в маршрут. Время растёт пропорционально числу рёбер, и именно так компьютеры находят эйлеровы пути.

    Часто задаваемые вопросы

    Чем эйлеров путь отличается от эйлерова цикла?

    Оба проходят каждое ребро графа ровно один раз. Эйлеров цикл заканчивается там, где начался; эйлеров путь — в другом месте. У связного графа есть цикл, когда степень каждой вершины чётная, и путь, когда ровно две вершины имеют нечётную степень; тогда путь идёт из одной в другую.

    Почему по семи мостам Кёнигсберга нельзя пройти по одному разу?

    Нарисуйте каждый участок суши вершиной, а каждый мост — ребром. У острова Кнайпхоф было пять мостов, у трёх других участков — по три, так что все четыре вершины нечётные. Прогулка может начинаться или заканчиваться только в нечётной вершине, а четырёх слишком много. Один дополнительный мост между двумя из них оставляет две нечётные вершины, и прогулка становится возможной.

    Сколькими способами можно нарисовать домик Деда Мороза?

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

    Что такое мост в графе?

    Ребро, удаление которого разбивает связный граф на две части. Алгоритм Флёри никогда не идёт по мосту среди оставшихся рёбер, пока у него есть другой выбор, иначе часть фигуры осталась бы позади. В этом приложении росчерку, застрявшему после слишком раннего прохода по мосту, сообщается, какой это был шаг.

    Может ли между двумя вершинами быть больше одного ребра?

    Да. Граф с параллельными рёбрами называется мультиграфом, и Кёнигсбергу он необходим: Кнайпхоф соединяли с каждым берегом два моста. В режиме Рисовать коснитесь двух вершин ещё раз, чтобы добавить между ними ещё одно ребро, до четырёх. Правило степеней работает так же и учитывает каждое ребро.

    Готовы попробовать?

    Откройте PictorX в своем браузере — установка не требуется, для запуска не требуется кредитная карта.

    Перейти в редактор