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