Готовимся к Всероссийским проверочным работам (ВПР) активно и с удовольствием! Сегодня предлагаю вашему вниманию одну из тех задач по теории графов, которая часто встречается у семиклассников и может показаться на первый взгляд очень сложной. Мы разберем её и найдем универсальный алгоритм, который поможет вам решать подобные задачи.
Вот сама задача, которую мы будем решать:
Нужно изготовить каркасную модель куба заданного размера с двумя диагоналями противоположных граней (см. рисунок), затратив наименьшее возможное количество проволоки. Проволоку можно гнуть под любым углом и сваривать в точках соединения. Какое наименьшее количество кусков проволоки нужно, чтобы изготовить модель, показанную на рисунке?
Рассмотрим данную конструкцию как граф. Чтобы решение стало простым и понятным, нам нужно вспомнить пару базовых определений и одну очень важную теорему.
Граф — это изображение объектов и связей между ними с помощью точек и линий. Точки в графе называются вершинами графа. Некоторые (не обязательно все) вершины соединены линиями. Эти линии называются рёбрами графа.
Степень вершины в графе — это количество исходящих из неё рёбер.
Для решения задач на «рисование одним росчерком» или изготовление каркаса из проволоки существует фундаментальная теорема:
Теорема Эйлера:
Путь, проходящий через все рёбра графа ровно по одному разу, существует тогда и только тогда, когда в этом графе не более двух нечётных вершин (то есть вершин, из которых выходит нечётное число линий).
Переходим к решению. Посчитаем степень каждой вершины на нашем рисунке:
• У нас 4 вершины чётной степени (в них сходятся по 4 ребра).
• И 4 вершины нечётной степени (в них сходятся по 3 ребра).
Почему это важно?
В вершине с нечётной степенью кусок проволоки не может просто пройти насквозь: он должен там либо начаться, либо закончиться. А так как у любого куска проволоки всего два конца, то на один кусок приходится максимум две нечётные вершины.
Разберем нашу конструкцию на части.
Наша цель — оставить в графе не более двух нечётных вершин, чтобы остальную часть можно было изготовить из одного цельного куска. Отметим две нечетные вершины на рисунке:
Заметим, что теперь остались две вершины нечетной степени. Давайте мысленно «отложим в сторону» одно ребро, соединяющее две эти нечётные вершины (на рисунке ниже оно выделено красным цветом).
Что произошло с нашими вершинами?
Посмотрите на точки, которые соединяло это ребро: их степень уменьшилась с 3 до 2. Теперь эти вершины стали чётными!
В итоге во всей остальной фигуре у нас осталось всего две нечётные вершины. А согласно теореме Эйлера, такой граф можно изготовить из одного непрерывного куска проволоки.
Итак, давайте подведем итоги нашего исследования.
После того как мы мысленно убрали одно ребро (красную проволоку), соединяющее две нечётные вершины, в оставшейся части конструкции у нас осталось всего две нечётные вершины.
Как мы помним из теоремы Эйлера, граф, в котором есть ровно две нечётные вершины, можно полностью пройти (изготовить из одного куска проволоки), начав путь в одной из них и закончив в другой.
Таким образом, чтобы изготовить всю каркасную модель, нам понадобится:
• Один кусок проволоки для той самой красной линии, которую мы отложили вначале.
• Еще один непрерывный кусок проволоки для всей оставшейся части конструкции.
Итого: 1 + 1 = 2 куска проволоки.
Ответ: Чтобы изготовить данную каркасную модель куба, потребуется 2 куска проволоки.
Универсальный метод: формула для любых моделей
Метод откладывания рёбер, который мы разобрали, отлично показывает логику процесса. Но что делать, если перед нами будет не куб, а гораздо более сложная многогранная конструкция, где нечётных вершин будет десять или двадцать? Вручную перебирать кусочки станет слишком долго и сложно.
Универсальная формула.
Давайте ещё раз вспомним: у каждого куска проволоки есть два конца. В вершинах нечетной степени он либо начинается, либо заканчивается. Значит, один кусок проволоки всегда берёт на себя ровно две нечётные вершины.
Отсюда вытекает простейшее правило:
Количество кусков проволоки = N/2, где N — общее количество вершин с нечётной степенью.
Проверим формулу на нашей задаче:
1. Мы насчитали в кубе с двумя диагоналями 4 нечётные вершины.
2. Применяем формулу: 4 / 2 = 2.
3. Ответ совпал!
Важный нюанс:
Если вдруг в вашей модели все вершины оказались чётными (то есть N = 0), это значит, что всю фигуру можно обернуть одним куском проволоки и вернуться в ту же точку, откуда начали. В этом случае ответ всегда будет 1.
Теперь, какой бы сложной ни была каркасная модель в задании ВПР, вы сможете решить её за считанные секунды: просто посчитайте вершины с нечетной степенью и делите их количество пополам!
Спасибо за внимание, до новых встреч.
Буду рада вашим комментариям, лайкам и подписке на канал, а также если вы поддержите мой канал!
Каналы в мессенджере Макс и Телеграм. Присоединяйтесь, буду рада видеть вас там!