В некоторой стране количество городов равно 47 . железнодорожная компания решила соединить все эти города. строительство железного полотна стоит дорого поэтому дороги буду…
В некоторой стране количество городов равно 47 . железнодорожная компания решила соединить все эти города. строительство железного полотна стоит дорого поэтому дороги буду спроектированы так чтобы из каждого города можно было попасть в любой, сделав не более двух пресадок. сколько железных дорог нужно будет проложить компаниии
Ответ: 46 дорог.
Пояснение:
Любая связная сеть из 47 городов требует как минимум 46 дорог (ребер), чтобы соединить все города в одну компоненту. Это базовый факт о связных графах: n городов требуют не менее n-1 ребер.
Можно построить сеть с exactly 46 дорог, удовлетворяющую условию: выберите один город как «центр» и соедините его прямым ребром со всеми 46 другими городами. Получится звездообразная структура (звезда) с центром и 46 лучами.
Проверка условия о пересадках:
- между центром и любым городом расстояние 1 ребро (0 пересадок).
- между любыми двумя непцентральными городами путь через центр: два ребра, то есть 1 пересадка.
- максимальное число пересадок среди любых пар городов равно 1, что удовлетворяет требованию «не более двух пересадок».
Следовательно, минимальное возможное число дорог равно 46, и такое же число достигается звездой с центром в одном городе.
