В некоторой стране количество городов равно 38.Железнодорожная компания решила соединить все эти города.Строительство железного полотна стоит дорого, поэтому их количество должно…
В некоторой стране количество городов равно 38.Железнодорожная компания решила соединить все эти города.Строительство железного полотна стоит дорого, поэтому их количество должно быть минимальным.Но компания заботится и об удобстве жителей страны,поэтому дороги буду спроектированы так, чтобы из каждого города можно было попасть в любой, сделав не более двух пересадок.Сколько железных дорог нужно будет проложить компании?
Дано: количество городов = 38.
Для решения этой задачи используем графовую теорию. Мы можем рассматривать города как вершины графа, а дороги между городами — как рёбра этого графа. Условие о том, что из каждого города должно быть возможно добраться до любого другого с не более чем двумя пересадками, означает, что граф должен быть связным и его диаметр (максимальное кратчайшее расстояние между любыми двумя вершинами) не превышает 2.
Так как максимальное расстояние между двумя вершинами в неориентированном графе с n вершинами равно n-1 (путь от любой вершины к любой другой должен проходить через n-2 пересечения), то условие двух пересадок означает, что диаметр графа равен 2.
Для такого графа диаметр равен 2, значит, он представляет собой некую центральную вершину (которая соединяется со всеми другими вершинами) и вершины, соединенные с этой центральной вершиной. Таким образом, граф выглядит как "звезда" с 1 центральной вершиной и (n-1) вершинами-листьями.
Итак, чтобы соединить все 38 городов согласно условию задачи, железнодорожной компании потребуется проложить 37 железных дорог, так как в центре "звезды" будет один город, соединенный с остальными 37 городами-листьями.
