На рисунке показана схема улиц небольшого города. Какое наименьшее число улиц можно закрыть на ремонт так, чтобы маршрут автобуса проходил бы ровно по одному разу по каждой улице, на которой нет ремонта?

Решение:

Задача сводится к поиску минимального покрытия рёбер графа. На схеме изображён граф, где точки — перекрёстки, а линии — улицы.

Чтобы автобус проехал ровно по одному разу по каждой улице, на которой нет ремонта, нам нужно выбрать такой набор улиц для ремонта, чтобы оставшиеся улицы образовывали Эйлеров цикл или Эйлеров путь.

Сначала посчитаем степени всех вершин (количество улиц, сходящихся в каждой точке):

• Вершина 1 (верхний левый): степень 2
• Вершина 2 (верхний правый): степень 2
• Вершина 3 (левая средняя): степень 3
• Вершина 4 (центральная): степень 4
• Вершина 5 (правая средняя): степень 3
• Вершина 6 (нижняя левая): степень 2
• Вершина 7 (нижняя правая): степень 2

В графе есть две вершины нечётной степени (3 и 5). Чтобы получился Эйлеров путь, нужно, чтобы все вершины имели чётную степень, или чтобы были ровно две вершины нечётной степени.

Если мы закроем улицы, соединяющие вершины 3 и 5 с центральной вершиной (вершина 4), то степени вершин 3 и 5 станут 2 (чётными), а степень вершины 4 станет 2 (чётной).

Таким образом, если закрыть 2 улицы (те, что ведут от вершин 3 и 5 к вершине 4), то оставшиеся улицы образуют граф, в котором все вершины будут иметь чётную степень. В таком графе существует Эйлеров цикл, то есть автобус сможет проехать по каждой оставшейся улице ровно один раз.

Ответ: 2