Фестиваль идей. Одним росчерком

Определения и обозначения

Рисунок одним росчерком — это фигура, которую можно начертить одной непрерывной линией, не отрывая карандаш от бумаги и не проводя ни один отрезок повторно. Такое условие превращает обычный рисунок в задачу на поиск маршрута. Нужно не просто соединить точки, а пройти по каждому ребру ровно один раз.

Вершина — точка, в которой заканчивается или начинается отрезок либо сходятся несколько отрезков. Вершины обозначают буквами, например A, B и C. Они нужны, чтобы описывать маршрут словами и считать, сколько линий связано с каждой точкой.

Ребро — отрезок, соединяющий две вершины. Если из вершины выходит три отрезка, её степень равна 3; если четыре — степень равна 4. Подсчёт степеней позволяет заранее понять, можно ли пройти всю сеть одним росчерком.

Чётная вершина имеет чётную степень, а нечётная вершина — нечётную. В обычном маршруте в вершину нужно войти по одному ребру и выйти по другому, поэтому использованные рёбра удобно объединяются в пары. Исключение составляют начало и конец пути: там одно ребро может остаться без пары.

Как это устроено

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

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

Если нечётных вершин четыре или больше, одного маршрута не хватит. Каждая такая вершина требует особого места для начала или окончания движения, а у одного росчерка таких мест может быть не более двух. Поэтому подсчёт нечётных вершин часто позволяет сразу доказать невозможность, не перебирая все варианты движения.

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

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

Признаки возможности начертить фигуру одним росчерком

Сначала проверь связность рисунка: все его рёбра должны принадлежать одной соединённой части. Затем посчитай степень каждой вершины и внеси результат в подходящую строку таблицы. Если нечётных вершин две, начинать следует с одной из них; если их нет, начало можно выбрать произвольно.

Разбор задач

Задача 1

Дана сеть с вершинами A, B, C и D и рёбрами AB, BC, CD и DA. Требуется выяснить, можно ли начертить её одним росчерком. Линии образуют замкнутый четырёхугольник, но решение лучше подтвердить подсчётом степеней.

1. У вершины A есть рёбра AB и AD, поэтому её степень равна 2. У B также два ребра: BA и BC, значит, степень B равна 2.
2. У C соединения CB и CD, поэтому степень C равна 2. У D соединения DC и DA, значит, степень D тоже равна 2.
3. Все четыре вершины чётные, а сеть связна. Следовательно, можно начать, например, в A и закончить там же.
4. Один из маршрутов таков: A — B — C — D — A. Каждое ребро использовано ровно один раз, карандаш всё время остаётся на бумаге.

Ответ: да, фигуру можно начертить одним росчерком; например, по маршруту A — B — C — D — A.

Задача 2

Рассмотрим сеть с рёбрами AB, AC, AD, BE и CE. Нужно определить, возможен ли одноросчерковый маршрут. Здесь полезно не пытаться сразу угадывать путь, а сначала исследовать вершины.

1. Степень A равна 3, потому что к ней подходят AB, AC и AD. Степень B равна 2: рёбра BA и BE. Степень C равна 2: рёбра CA и CE.
2. У вершины D только одно ребро DA, поэтому её степень равна 1. У E два ребра EB и EC, значит, степень E равна 2.
3. Нечётными оказались A и D, то есть всего их две. Сеть связна, поэтому маршрут должен начинаться в A или D и заканчиваться в другой из этих вершин.
4. Подходит путь D — A — C — E — B — A. Он проходит по рёбрам DA, AC, CE, EB и BA без повторений.

Ответ: да; один из вариантов — D — A — C — E — B — A.

Типичные ошибки

Ошибка 1. Считать вершиной каждую точку на рисунке. Иногда ученик отмечает точку внутри прямого отрезка, хотя в ней нет поворота или соединения с другой линией. Такая точка не меняет маршрут и не должна учитываться отдельно. Проверь, действительно ли в выбранной точке сходятся разные рёбра.

Ошибка 2. Проверять только число линий, но не их связность. Две отдельные фигуры могут иметь подходящее число нечётных вершин, но перейти из одной в другую невозможно. Перед подсчётом степеней убедись, что между всеми частями есть путь. Если из одной части нельзя добраться до другой, один росчерк невозможен.

Ошибка 3. Повторно проходить уже использованное ребро. Возвращение в вершину разрешено, а повторение самого отрезка — нет. Отмечай каждое пройденное ребро и не путай его с вершиной. В конце пересчитай все рёбра: каждое должно встретиться в маршруте ровно один раз.

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

Связь с другими темами

Задачи на один росчерк связаны с геометрией, потому что в них рассматриваются отрезки, точки, пересечения и замкнутые фигуры. Они также используют идеи комбинаторики: нужно перебрать или обоснованно исключить варианты маршрута. Навык подсчёта чётных и нечётных чисел помогает быстро исследовать степени вершин. В информатике такая сеть похожа на граф, а маршрут по всем рёбрам называют эйлеровым путём.

Что запомнить

• Одним росчерком проходят по каждому ребру ровно один раз, не отрывая карандаш.
• Вершина — точка соединения, ребро — соединяющий её отрезок.
• При нуле нечётных вершин маршрут начинается и заканчивается в одной точке.
• При двух нечётных вершинах начинать нужно с одной из них, а заканчивать — в другой.
• Если нечётных вершин больше двух или сеть распадается на части, один росчерк невозможен.
• После построения маршрута проверь каждое ребро и убедись, что оно использовано ровно один раз.