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

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

р. Прегель

Рис. 146

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

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

Обозначим вершины графа, соответствующие участкам суши на рисунке:
А — Северный берег (верхний);
Б — Южный берег (нижний);
В — Западный остров (левый);
Г — Восточный остров (правый).

Теперь посчитаем количество мостов (рёбер), соединяющих эти участки суши:
- Между Северным берегом (А) и Западным островом (В) — 2 моста.
- Между Южным берегом (Б) и Западным островом (В) — 2 моста.
- Между Западным островом (В) и Восточным островом (Г) — 1 мост.
- Между Северным берегом (А) и Восточным островом (Г) — 1 мост.
- Между Южным берегом (Б) и Восточным островом (Г) — 1 мост.

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

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

Посчитаем степень каждой вершины в нашей задаче:
- Степень вершины А (Северный берег) = $2$ (к острову В) $+ 1$ (к острову Г) $= 3$ (нечётная).
- Степень вершины Б (Южный берег) = $2$ (к острову В) $+ 1$ (к острову Г) $= 3$ (нечётная).
- Степень вершины В (Западный остров) = $2$ (к берегу А) $+ 2$ (к берегу Б) $+ 1$ (к острову Г) $= 5$ (нечётная).
- Степень вершины Г (Восточный остров) = $1$ (к берегу А) $+ 1$ (к берегу Б) $+ 1$ (к острову В) $= 3$ (нечётная).

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

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