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

Решение:

Эта задача является классическим примером задачи о графах, в частности, о проходимости графа. В данной задаче острова представляют вершины графа, а мосты — рёбра.

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

Рассмотрим степень каждой вершины (острова):

• Остров 1: соединён с 3 мостами (степень 3 - нечётная)
• Остров 2: соединён с 5 мостами (степень 5 - нечётная)
• Остров 3: соединён с 3 мостами (степень 3 - нечётная)
• Остров 4: соединён с 3 мостами (степень 3 - нечётная)

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

Ответ: Нет, нельзя совершить такую прогулку.