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

Ответ:

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

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

Ответ:

Нет, нельзя.

Отлично! Теперь ты знаешь, почему нельзя пройти по всем мостам в Кенигсберге даже без возврата!