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