Олимпиадная задача по теории графов: максимум городов при ограниченных авиалиниях
Задача
В некотором государстве система авиалиний устроена таким образом, что каждый город соединен авиалиниями не более чем с тремя другими, и из каждого города можно попасть в любой другой, сделав не более одной пересадки. Какое наибольшее количество городов может быть в этом государстве?
Решение
Оценка. Из фиксированного города А можно попасть напрямую не более чем в три города, а с одной пересадкой – еще не более чем в 3·2 = 6 городов. Таким образом, всего городов может быть не более десяти.
Пример сети из 10 городов см. на рисунке.
Ответ
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет