В центре Кёнигсберга (современный Калининград) расположились два больших острова, омываемых рекой Прегель (современное название Преголя). Они соединены друг с другом и с берегами семью мостами. Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз и при этом вернуться в исходную точку?

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

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

• Первый берег соединен с островами тремя мостами.
• Второй берег соединен с островами двумя мостами.
• Первый остров соединен с берегами тремя мостами и со вторым островом одним мостом.
• Второй остров соединен с берегами двумя мостами и с первым островом одним мостом.

Получаем следующие степени вершин:

• Вершина 1 (первый берег): 3
• Вершина 2 (второй берег): 2
• Вершина 3 (первый остров): 4
• Вершина 4 (второй остров): 5

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

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