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

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

Рис. 145

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

Сначала определим количество дверей в каждом зале, что в теории графов называется степенью вершины:

• Зал 1: 2 двери (четная степень)
• Зал 2: 3 двери (нечетная степень)
• Зал 3: 3 двери (нечетная степень)
• Зал 4: 2 двери (четная степень)
• Зал 5: 3 двери (нечетная степень)
• Зал 6: 4 двери (четная степень)
• Зал 7: 4 двери (четная степень)
• Зал 8: 3 двери (нечетная степень)
• Зал 9: 2 двери (четная степень)
• Зал 10: 3 двери (нечетная степень)
• Зал 11: 3 двери (нечетная степень)
• Зал 12: 2 двери (четная степень)

Мы видим, что есть шесть залов с нечетным количеством дверей: 2, 3, 5, 8, 10 и 11.

Где нужно начать и где закончить осмотр?

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

Однако в задаче требуется обойти все *залы*, а не все *двери*. Формулировка вопроса "Где нужно начать и где закончить?" указывает на то, что начальная и конечная точки обладают особыми свойствами. В задачах такого типа этими особыми точками как раз и являются вершины с нечетной степенью. Поэтому следует выбрать для начала и конца маршрута два из шести залов с нечетным числом дверей.

Ответ: Начать осмотр нужно в одном из залов с нечетным количеством дверей (например, в зале 2, 3, 5, 8, 10 или 11) и закончить осмотр в другом зале с нечетным количеством дверей.

Найдите один из возможных маршрутов

Выберем в качестве начальной точки зал №2, а в качестве конечной — зал №11 (оба имеют по 3 двери). Можно построить следующий маршрут, который удовлетворяет всем условиям задачи:

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

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

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