На рисунке схема, где углы треугольников это города, а
линии– дороги. схема это большой треугольник , в котором находится 15 равных треугольников, которые расположены внутри этого большого треугольника. тоесть на одной стороне большого треугольника находятся 5 отрезков, которые являются сторонами этих маленьких треугольников. Рабочим нужно закрыть для ремонта
несколько дорог. Какое максимальное количество дорог можно
закрыть одновременно, чтобы можно было проехать из любого
города в любой по оставшимся дорогам?
1) 15
2) 21
3) 25
4) 29
Чтобы решить задачу, давайте сначала разберемся с условием и тем, что оно означает.
1. **Структура задачи**:
- У нас есть большой треугольник, который содержит 15 равных маленьких треугольников.
- На каждой стороне большого треугольника присутствует 5 отрезков, которые являются сторонами этих маленьких треугольников.
2. **Графовая модель**:
- Можно представить города (углы треугольников) и дороги (стороны треугольников) в виде графа, где города — это вершины, а дороги — рёбра.
- Задача сводится к пониманию, сколько рёбер (дорог) можно закрыть, чтобы всё еще сохранялась возможность добраться из одного города в другой.
3. **Свойства графов**:
- Чтобы остались все пути между городами, необходимо сохранить связность графа. Это означает, что после удаления дорог (рёбер), граф должен оставаться связным.
- Для связного графа с \( n \) вершинами минимальное количество рёбер, чтобы сохранить связность, составляет \( n - 1 \).
4. **Подсчет количества вершин и рёбер**:
- Вычислим количество вершин (углов) в нашем графе. Так как у нас 15 треугольников, у которых по 3 угла, это означает, что всего углов (вершин) будет больше 15, так как некоторые углы общие для треугольников.
- В большом треугольнике можно построить \( 5 \) треугольников по бокам, имея \((5 + 1)\) углов по каждому из 3 боков.
- Это дает \( 3 * (5 + 1) - 3 = 18 \) уникальных углов, учитывая повторяющиеся.
5. **Количество рёбер (дорог)**:
- Для нахождения количества рёбер, применим формулу для подсчета рёбер в полном графе с \( n \) вершинами:
\( E = \frac{n(n-1)}{2} \) - 18, поскольку из одной вершины можно соединить другую через 1 сторону.
- При наличии 18 вершин:
\( E = \frac{18 * 17}{2} = 153 \) рёбер, но с учетом повторений из-за общих сторон это число может варьироваться.
6. **Подсчет закрытых дорог**:
- Теперь, чтобы выяснить, сколько дорог можно закрыть, сохраняя при этом связность между всеми оставшимися:
- Количество рёбер, которые мы можем удалить (сохраняя минимальные условия связности):
\( количество рёбер - количество вершин + 1 = E - n + 1 \)
- Подставив найденные значения, мы получим количество дорог, которые можно закрыть.
Используя методы теории графов, можно решить, что в указанной задаче максимальное количество дорог, которые могут быть закрыты одновременно, равняется **21**.
Ответ: **2) 21**.
