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

Для решения этой задачи, нам нужно найти минимальное количество улиц, которые нужно закрыть, чтобы можно было пройти по всем остальным улицам ровно один раз. Это эквивалентно нахождению эйлерова пути в графе. Эйлеров путь существует, если в графе не более двух вершин с нечетной степенью (количеством инцидентных ребер). Посмотрим на граф: посчитаем степени вершин (количество улиц, сходящихся в каждой точке): * Есть 4 вершины степени 3. Чтобы получить эйлеров путь, нужно, чтобы осталось не более двух вершин с нечетной степенью. Сейчас их 4. Чтобы уменьшить число нечетных вершин, нужно удалить ребра, инцидентные этим вершинам. Чтобы избавиться от двух нечетных вершин, достаточно удалить два ребра, каждое из которых инцидентно одной из этих вершин. Тогда степень каждой из этих вершин уменьшится на 1, и они станут четными. Чтобы избавиться от 4-х нечетных вершин нужно удалить минимум 2 ребра, каждое из которых инцидентно одной из этих вершин. Следовательно, наименьшее число улиц, которые нужно закрыть – 2.