В некоторой стране количество городов равно 10. Железнодорожная компания решила соединить все эти города. Строительство железного полотна стоит дорого, поэтому их количество должно быть минимальным. Но компания заботится и об удобстве жителей страны, поэтому дороги будут спроектированы так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок. Сколько железных дорог нужно будет проложить компании?

Question

Вопрос:

В некоторой стране количество городов равно 10. Железнодорожная компания решила соединить все эти города. Строительство железного полотна стоит дорого, поэтому их количество должно быть минимальным. Но компания заботится и об удобстве жителей страны, поэтому дороги будут спроектированы так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок. Сколько железных дорог нужно будет проложить компании?

Ответ:

ФИО:Телефон:Емаил:Полное описание сути нарушения прав (почему распространение данной информации запрещено Правообладателем):

Accepted Answer

Для решения задачи воспользуемся графовой теорией. Так как требуется соединить 10 городов с условием, что между любыми двумя городами не более двух пересадок, минимальный граф, удовлетворяющий этому условию, представляет собой дерево с центральным узлом. В таком случае минимальное количество дорог равно количеству городов минус 1: 10 - 1 = 9. Таким образом, компании нужно проложить 9 железных дорог.