Задача 070 — Задачи на Графы

B стране $n$ городов, некоторые пары из них соединены дорогами с двухсторонним движением. В некоторых городах построены школы, назовём такие города важными. Оказалось, что 1) из каждого города можно добраться до любого другого; 2) каждый не важный город соединён дорогой с важным городом. Для какого наименьшего $k$ всегда можно закрыть все дороги, кроме некоторых $k$ , на ремонт так, чтобы эти два условия сохранились?

Подсказка

Можно оставить только остовное дерево.

Решение

Ответ: $n-1$ . Решение. Рассмотрим граф, вершинами которого являются города, ребрами — дороги. Понятно, что $k \geqslant n-1$ , в противном случае граф на оставшихся ребрах не будет связным. Докажем, что в этом графе всегда можно выделить остовное дерево, удовлетворяющее условиям. Будем последовательно удалять ребра из графа. Пусть в графе к текущему моменту есть цикл, проходящий по вершинам $C_{1} C_{2} \ldots C_{m} C_{1}$ . Предположим, что мы не можем удалить ребро $C_{i} C_{i+1}$ (считаем, что $C_{m+1}=C_{1}$ ) с сохранением всех условий. Тогда один из городов $C_{i}$ и $C_{i+1}$ должен быть важным, а другой — не важным. Поэтому если мы не можем удалить ни одно из ребер цикла, то в нем чередуются важные и не важные города. В этом случае удалим любое ребро из нашего цикла. Каждый не важный город будет по-прежнему соединен с важным. В какой-то момент в графе не останется циклов, а все условия будут выполнены. Поэтому оставшийся граф дерево, и ребер в нем ровно $n-1$ .