Страница 160 - гдз по математике 5 класс учебник Никольский, Потапов

3.116. Придумайте свои фигуры, которые можно нарисовать, не отрывая карандаша от бумаги и не проводя по линии дважды.

Задачу о рисовании фигур одним росчерком можно решить, проанализировав их с точки зрения теории графов. Ключевым понятием является «вершина» — точка, в которой соединяются линии. Количество линий, сходящихся в вершине, называется ее степенью. Вершина бывает четной (если ее степень 2, 4, 6 и т.д.) или нечетной (если ее степень 1, 3, 5 и т.д.).

Фигуру можно нарисовать, не отрывая карандаша и не проводя по линии дважды, если она является связной (состоит из одного куска) и имеет не более двух нечетных вершин.

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

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

Фигура 1: «Бабочка»

Эта фигура состоит из двух треугольников, соприкасающихся в одной общей вершине. У этой фигуры 5 вершин. Давайте проанализируем их степени:
- Центральная (общая) вершина: в ней сходятся 4 линии (по две от каждого треугольника). Ее степень — 4 (четная).
- Остальные 4 вершины («крылья бабочки»): в каждой из них сходятся по 2 линии. Их степень — 2 (четная).
Все вершины этой фигуры — четные. Следовательно, «Бабочку» можно нарисовать одним росчерком, причем можно начать и закончить в любой точке.

Фигура 2: «Домик»

Эта фигура состоит из квадрата («стены») и треугольника («крыша»), построенного на верхней стороне квадрата. У этой фигуры 5 вершин:
- Две нижние вершины квадрата: в каждой сходятся по 2 линии (две стороны). Их степень — 2 (четная).
- Вершина треугольника («конёк»): в ней сходятся 2 линии (скаты крыши). Ее степень — 2 (четная).
- Две верхние вершины квадрата (они же — основание крыши): в каждой из них сходятся 3 линии (боковая стена, верхняя стена-основание, скат крыши). Их степень — 3 (нечетная).
В этой фигуре ровно две нечетные вершины. Значит, ее можно нарисовать одним росчерком, если начать в одной из верхних вершин квадрата и закончить в другой.

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

3.117. Почтальон разнёс почту во все дома деревни, после чего зашёл с посылкой к Феде. На рисунке 149 показаны все тропинки, по которым проходил почтальон, причём, как оказалось, ни по одной из них он не проходил дважды. В каком доме живёт Федя? Каков мог быть маршрут почтальона?

Рис. 149

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

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

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

Если в графе более двух вершин с нечётной степенью, эйлеров путь невозможен.

Проанализируем наш граф. Найдём степени каждой вершины:

• Почта: 5 тропинок (к домам 1, 3, 4, 6, 7). Степень $deg(П) = 5$ (нечётная).
• Дом 1: 3 тропинки (к Почте, домам 2, 7). Степень $deg(1) = 3$ (нечётная).
• Дом 2: 2 тропинки (к домам 1, 3). Степень $deg(2) = 2$ (чётная).
• Дом 3: 3 тропинки (к Почте, домам 2, 4). Степень $deg(3) = 3$ (нечётная).
• Дом 4: 3 тропинки (к Почте, домам 3, 5). Степень $deg(4) = 3$ (нечётная).
• Дом 5: 3 тропинки (к домам 4, 6, 7). Степень $deg(5) = 3$ (нечётная).
• Дом 6: 3 тропинки (к Почте, домам 5, 7). Степень $deg(6) = 3$ (нечётная).
• Дом 7: 4 тропинки (к Почте, домам 1, 5, 6). Степень $deg(7) = 4$ (чётная).

В данном графе шесть вершин имеют нечётную степень: Почта, дом 1, дом 3, дом 4, дом 5 и дом 6. Вершины с чётной степенью — дом 2 и дом 7.

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

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

Это означает, что условия задачи противоречивы. Вероятнее всего, в условии или на рисунке допущена ошибка. При данных условиях определить дом Феди невозможно.

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

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

Таким образом, почтальон не мог проложить такой маршрут, который описан в задаче. Любая попытка построить такой маршрут приведёт либо к тому, что некоторые тропинки останутся не пройденными, либо к тому, что по каким-то тропинкам придётся пройти более одного раза.

Ответ: Маршрута, удовлетворяющего всем условиям задачи, не существует.

3.118. Экскурсоводу нужно выбрать маршрут по залам музея так, чтобы обойти все залы, не проходя ни через одну дверь дважды. Где нужно начать и где закончить осмотр? Найдите один из возможных маршрутов (рис. 150).

1 2 3 4

5 6 7 8

9 10 11 12

Рис. 150

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

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

Давайте посчитаем количество дверей в каждом зале (то есть определим степень каждой вершины графа):

• Залы 1, 4, 9, 12 имеют по 2 двери (чётные вершины).
• Залы 6, 7 имеют по 4 двери (чётные вершины).
• Залы 2, 3, 5, 8, 10, 11 имеют по 3 двери (нечётные вершины).

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

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

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

Примером маршрута, который позволяет посетить все залы без повторного прохода через двери, является следующая последовательность:

9 → 10 → 11 → 12 → 8 → 7 → 6 → 5 → 1 → 2 → 3 → 4.

Этот маршрут проходит через все 12 залов. Он начинается в зале 9 и заканчивается в зале 4. Каждый переход осуществляется через новую дверь, которая не использовалась ранее в маршруте.

Ответ: Один из возможных маршрутов: 9 → 10 → 11 → 12 → 8 → 7 → 6 → 5 → 1 → 2 → 3 → 4. При таком маршруте осмотр начинается в зале 9 и заканчивается в зале 4.

3.119. Задача Л. Эйлера. Можно ли по-очерёдно обойти все семь мостов г. Кёнигсберга (ныне Калининград), соединяющих районы этого города с островами на реке Прегель (рис. 151), проходя по каждому мосту только один раз?

р. Прегель

Рис. 151

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

На схеме (рис. 151) можно выделить четыре участка суши (вершины графа):

• Вершина A: верхний берег реки.
• Вершина B: нижний берег реки.
• Вершина C: левый остров.
• Вершина D: правый остров.

Теперь посчитаем количество мостов (рёбер), которые ведут к каждому участку суши. Это число называется степенью вершины.

• Вершина A (верхний берег) соединена 2 мостами с островом C и 1 мостом с островом D. Степень вершины A: $deg(A) = 2 + 1 = 3$.
• Вершина B (нижний берег) соединена 2 мостами с островом C и 1 мостом с островом D. Степень вершины B: $deg(B) = 2 + 1 = 3$.
• Вершина C (левый остров) соединена 2 мостами с берегом A, 2 мостами с берегом B и 1 мостом с островом D. Степень вершины C: $deg(C) = 2 + 2 + 1 = 5$.
• Вершина D (правый остров) соединена 1 мостом с берегом A, 1 мостом с берегом B и 1 мостом с островом C. Степень вершины D: $deg(D) = 1 + 1 + 1 = 3$.

Таким образом, мы получили четыре вершины со степенями 3, 3, 5, 3. Все четыре вершины имеют нечётную степень.

Согласно теореме, доказанной Эйлером, обход графа с прохождением по каждому ребру ровно один раз (такой маршрут называется Эйлеровым путём) возможен только при выполнении одного из двух условий:

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

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

Ответ: Нет, обойти все семь мостов, проходя по каждому только один раз, невозможно.