Задача
Как соединить 50 городов наименьшим числом авиалиний так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок?
Решение
Выделим один город и соединим его авиалинией с каждым из остальных 49 городов. Для этого потребуется 49 авиалиний.
Меньшим числом авиалиний обойтись нельзя. Действительно, согласно задаче 131098 г) в связном графе с 50 вершинами не менее 49 рёбер.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет