Страница 92, часть 2 - гдз по алгебре 7-9 класс учебник часть 1, 2 Высоцкий, Ященко

144 Не отрывая карандаша от бумаги и не проводя одну линию дважды, нарисуйте фигуры, изображённые на рисунке 38.

а) Открытый конверт

б) Квадраты Льюиса Кэрролла

Рисунок 38

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

Критерий существования эйлерова пути (или цикла) связан со степенями вершин графа (точек, в которых соединяются или пересекаются линии). Степень вершины — это количество линий (рёбер), выходящих из неё.

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

а) Открытый конверт

Рассмотрим фигуру «Открытый конверт» как граф. Вершинами будут углы и точки пересечения линий. У этой фигуры 5 вершин: четыре угла основания и верхняя вершина «крышки» конверта.

Подсчитаем степени (количество линий, сходящихся в каждой точке) для каждой вершины:

• Нижняя левая вершина: 3 линии (левая сторона, нижняя сторона, диагональ). Степень = 3 (нечётная).
• Нижняя правая вершина: 3 линии (правая сторона, нижняя сторона, диагональ). Степень = 3 (нечётная).
• Верхняя левая вершина: 4 линии (левая сторона, верхняя сторона, диагональ, сторона «крышки»). Степень = 4 (чётная).
• Верхняя правая вершина: 4 линии (правая сторона, верхняя сторона, диагональ, сторона «крышки»). Степень = 4 (чётная).
• Верхняя вершина «крышки»: 2 линии. Степень = 2 (чётная).

В этом графе ровно две вершины с нечётной степенью (нижние углы). Согласно критерию, эйлеров путь существует. Это означает, что фигуру можно нарисовать одним росчерком, если начать в одной из нижних вершин и закончить в другой.

Пример последовательности рисования (начиная с левого нижнего угла):

1. Из левого нижнего угла провести левую боковую сторону вверх.
2. Оттуда — левую сторону «крышки» конверта до верхней точки.
3. Из верхней точки — правую сторону «крышки» вниз до правого верхнего угла.
4. Далее — верхнюю сторону конверта влево.
5. Из левого верхнего угла провести диагональ в правый нижний угол.
6. Затем — правую боковую сторону вверх.
7. Из правого верхнего угла провести вторую диагональ в левый нижний угол.
8. Наконец, провести нижнюю сторону вправо, закончив рисунок в правом нижнем углу.

Ответ: Да, эту фигуру можно нарисовать, не отрывая карандаша.

б) Квадраты Льюиса Кэрролла

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

Проанализируем степени всех вершин:

• Внешние углы: У фигуры есть 8 вершин, которые являются «внешними» углами (например, левый верхний угол самого большого квадрата). В каждой такой точке сходятся 2 линии. Степень каждой из этих вершин равна 2 (чётная).
• Точки пересечения: У фигуры также есть 8 точек, где стороны квадратов пересекаются друг с другом. В каждой такой точке пересечения сходятся 4 отрезка линий. Степень каждой из этих вершин равна 4 (чётная).

Таким образом, у всех вершин в этой фигуре чётная степень (либо 2, либо 4). Согласно критерию, в этом графе существует эйлеров цикл. Это означает, что фигуру можно нарисовать одним росчерком, причём можно начать в любой точке и закончить в той же самой точке.

Ответ: Да, эту фигуру можно нарисовать, не отрывая карандаша.

145 Придумайте способ обвести фигуру, изображённую на рисунке 39, одним росчерком (не отрывая карандаша от бумаги и не проводя одну линию дважды).

а) б) Рисунок 39

Для решения подобных задач используется раздел математики, называемый теорией графов. Фигура рассматривается как граф, в котором точки пересечения линий — это вершины, а сами линии — ребра. Согласно одной из основных теорем этой теории (теореме Эйлера), фигуру можно начертить одним росчерком (такой путь называется эйлеровым) тогда и только тогда, когда она является связной и содержит не более двух вершин с нечетным количеством отрезков (ребер), которые из них выходят. Если нечетных вершин нет совсем, то путь можно начать в любой вершине и закончить в ней же.

В фигуре а) имеется 7 вершин. Это углы внешнего семиугольника. Из каждой вершины проведены линии ко всем остальным 6 вершинам. Следовательно, степень каждой вершины, то есть количество выходящих из нее ребер, равна $6$. Так как 6 — это четное число, то все вершины в этой фигуре являются четными. Количество нечетных вершин равно нулю. Это означает, что фигуру можно начертить одним росчерком.

Ответ: Да, эту фигуру можно обвести одним росчерком, так как все ее вершины имеют четную степень (из каждой выходит по 6 линий).

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

В каждой точке пересечения сходятся две окружности. Это означает, что в каждой такой вершине пересекаются 4 дуги (по две от каждой окружности). Таким образом, степень каждой вершины в этой фигуре равна $4$. Поскольку 4 — это четное число, все вершины являются четными, и количество нечетных вершин равно нулю. Следовательно, условия для существования эйлерова пути выполняются.

Ответ: Да, эту фигуру можно обвести одним росчерком, так как все ее вершины (точки пересечения окружностей) имеют четную степень (в каждой пересекаются 4 дуги).

146 Пять участков отделены друг от друга заборами (см. план на рис. 40). Можно ли побывать на каждом участке, но при этом перелезть через каждый забор ровно один раз?

Рисунок 40. Участки и заборы

Для ответа на этот вопрос можно использовать теорию графов. Представим каждый из пяти участков, а также внешнюю территорию за забором, как вершины графа. Заборы, которые их разделяют, будут рёбрами этого графа. Таким образом, мы получаем граф с 6 вершинами (5 участков + 1 внешняя область).

Задача «побывать на каждом участке, но при этом перелезть через каждый забор ровно один раз» эквивалентна поиску эйлерова пути в этом графе. Эйлеров путь — это путь, который проходит по каждому ребру (забору) графа ровно один раз.

Согласно теореме Эйлера, эйлеров путь в связном графе существует тогда и только тогда, когда число вершин с нечётной степенью в этом графе равно нулю или двум. Степень вершины — это количество рёбер (заборов), которые к ней примыкают.

Давайте определим степени для всех вершин нашего графа:

• Верхний левый участок: имеет 3 забора (с верхним правым участком, с центральным и с внешней территорией). Его степень равна $3$ (нечётная).
• Верхний правый участок: имеет 3 забора (с верхним левым, с центральным и с внешней территорией). Его степень равна $3$ (нечётная).
• Нижний левый участок: имеет 3 забора (с нижним правым, с центральным и с внешней территорией). Его степень равна $3$ (нечётная).
• Нижний правый участок: имеет 3 забора (с нижним левым, с центральным и с внешней территорией). Его степень равна $3$ (нечётная).
• Центральный участок: имеет 4 забора (с каждым из четырёх других участков). Его степень равна $4$ (чётная).
• Внешняя территория: имеет 4 забора (с каждым из четырёх крайних участков). Её степень равна $4$ (чётная).

В получившемся графе четыре вершины имеют нечётную степень ($3, 3, 3, 3$). Поскольку количество вершин с нечётной степенью (четыре) не равно ни нулю, ни двум, то эйлеров путь в таком графе не существует.

Таким образом, выполнить поставленное условие невозможно.

Ответ: Нет, невозможно.

147 В Изумрудном городе шесть площадей. Каждая площадь соединена улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются.

а) Начертите возможный план Изумрудного города.

б) Можно ли устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды?

а) Данную задачу можно смоделировать с помощью теории графов. Площади Изумрудного города будут вершинами графа, а улицы — его рёбрами. Согласно условию, нам необходимо построить граф, в котором 6 вершин, и из каждой вершины выходит ровно 3 ребра (то есть степень каждой вершины равна 3). Кроме того, граф должен быть планарным, что означает, что его можно начертить на плоскости так, чтобы рёбра (улицы) не пересекались.

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


На этом плане кружками обозначены площади (пронумерованы от 1 до 6), а линиями — улицы. Каждая площадь соединена ровно с тремя другими, и улицы не пересекаются.

Ответ: Возможный план города представлен на рисунке выше.

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

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

• Если в графе нет вершин нечётной степени (все вершины имеют чётную степень), то существует эйлеров цикл — эйлеров путь, который начинается и заканчивается в одной и той же вершине.
• Если в графе ровно две вершины нечётной степени, то существует эйлеров путь, который начинается в одной из этих вершин, а заканчивается в другой.

В нашем случае граф, описывающий Изумрудный город, имеет 6 вершин (площадей). По условию, каждая площадь соединена с тремя другими, следовательно, степень каждой вершины равна 3. Число 3 является нечётным. Таким образом, в нашем графе все 6 вершин имеют нечётную степень.

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

Ответ: Нет, нельзя.