В стране 20172017 городов, некоторые из них соединены дорогами (при этом у каждой дороги концы в разных городах и никакие два города не соединяются друг с другом более чем одной дорогой). Назовем город меньше меньше провинциа...
В стране 20172017 городов, некоторые из них соединены дорогами (при этом у каждой дороги концы в разных городах и никакие два города не соединяются друг с другом более чем одной дорогой).
Назовем город <<провинциальным>>, если из него выходит не больше 3 дорог. Оказалось, что у любой дороги хоть одним из концов является провинциальный город.
Какое наибольшее количество дорог может быть в этой стране?
Гость
Ответ(ы) на вопрос:
ГостьПо теории графов:
20172017*(3/2)=20172017*1.5=30258025,5 Остаток 0.5 убираем, т.к. не может быть пол-дороги.
Ответ: 30258025 дорог - максимально.
Для проверки можно взять кубический граф Петерсена - на каждые 10 городов приходится 15 дорог: (20172017/10)*15=30258025,5
Не нашли ответ?
Похожие вопросы