Рассмотрим задачу:
У нас есть 11 городов, и нужно соединить их так, чтобы из любого города можно было добраться в любой другой, сделав не более двух пересадок. Строительство каждой дороги стоит определённых денег, и нужно найти минимальную сумму срз.
Задача фактически сводится к анализу графа:
- Города — вершины графа.
- Дороги — рёбра.
Требование: из любой вершины можно попасть в любую другую, сделав не более двух пересадок. Это соответствует тому, что граф должен иметь диаметр не более 2.
Шаг 1: Анализ требований
- Минимально связный граф (т. е. соединенных всех вершин) с диаметром ≤ 2.
Что значит диаметр графа ≤ 2?
- Расстояние между любыми двумя вершинами — не более 2.
Для этого существует всего два варианта разметки:
Все вершины напрямую соединены между собой (полный граф): тогда диаметр 1, и необходимы все узлы связаны рёбрами между собой, то есть ( C(11, 2) = 55 ) рёбер. Но это дорого.
Можно сделать так, чтобы из любого города было максимум две пересадки:
Лучшая стратегия — сделать одним "центральным" городом, который соединён со всеми остальными. Тогда:
- Центральный город связан со всеми другими 10 городами.
- Остальные города между собой не соединены напрямую, но из любого другого города в любой — за 1 дорогу (через центр).
Такой граф — звездчатый: один узел (центр) и остальные — его "лучи".
Диаметр этого графа равен 2, потому что:
- из любого города в центр — за 1 пересадку (один промежуточный этап).
- из одного города в другой — через центр за 2 пересадки, поскольку:
График:
A
/|\
/ | \
B C D
|
...
Шаг 2: Расчет стоимости
- Чтобы обеспечить связь с минимальной дорогой, необходимо построить звезду: один центр, соединённый с остальными городами.
- Количество дорог в такой модели: 10 (все города, кроме центра, соединены с центром).
Итог:
- Нужно проложить 10 дорог — по одной от центра к каждому из остальных городов.
Ответ:
Минимальное количество дорог, которое нужно проложить, чтобы из каждого города можно было попасть в любой другой за не более чем два пересадка, — 10.
