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

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.