Информатика 9 класс

Задача сводится к поиску вершин графа, которые покрывают все рёбра. Это известная задача теории графов, называемая задачей о покрытии множества (set cover problem).

Мы будем использовать жадный алгоритм для нахождения минимального покрытия. Идея заключается в том, чтобы на каждом шаге выбирать вершину, которая покрывает наибольшее количество ещё непокрытых рёбер.

Шаги алгоритма:
1. Начать с пустого набора покрытых вершин.
2. Пока остаются непокрытые рёбра:
- Найти вершину, которая покрывает максимальное количество оставшихся непокрытых рёбер.
- Добавить эту вершину в набор покрытых вершин.
- Обновить множество непокрытых рёбер, убрав те, которые покрыты выбранной вершиной.

Реализация на Python:

```python
def find_min_cameras(edges):
vertices = set()
covered_edges = set()

while edges:
best_vertex = max(vertices, key=lambda v: sum((u, v) in edges or (v, u) in edges for u in vertices))
vertices.add(best_vertex)
new_covered_edges = {(best_vertex, v) for v in vertices if (best_vertex, v) in edges}
edges -= new_covered_edges
covered_edges.update(new_covered_edges)

return ''.join(sorted(map(str, vertices)))

edges = {
(1, 2), (1, 3), (1, 4),
(2, 5), (2, 6),
(3, 7), (3, 8),
(4, 9), (4, 10),
(5, 11), (5, 12),
(6, 13), (6, 14),
(7, 15), (8, 15),
(9, 15), (10, 15),
(11, 15), (12, 15),
(13, 15), (14, 15)
}

print(find_min_cameras(edges))
```

Этот алгоритм находит минимальное покрытие вершин, удовлетворяющих условию задачи.