Задание 4 На рисунке изображён план здания. Сквозь дверные проёмы можно попасть из одного помещения в другое, выйти из здания или попасть снаружи внутрь. Определите, можно ли построить такой маршрут, чтобы пройти через каждый из 12 дверных проёмов ровно по одному разу?

Ответ: нет, нельзя

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

Подсчитаем количество дверных проемов для каждой комнаты:

• Комната 1 (верхняя левая): 3 проема
• Комната 2 (верхняя средняя): 3 проема
• Комната 3 (верхняя правая): 3 проема
• Комната 4 (средняя левая): 3 проема
• Комната 5 (нижняя): 4 проема

У нас 4 комнаты с нечетным числом дверных проемов (1, 2, 3 и 4). Так как число комнат с нечетным числом дверных проемов больше двух, то нельзя построить маршрут, проходящий через каждый дверной проем ровно один раз.

Ответ: нет, нельзя