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

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. В графе ровно две вершины с нечётной степенью. В этом случае маршрут должен начаться в одной из этих вершин и закончиться в другой.

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

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