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

Для решения этой задачи нужно воспользоваться понятием Эйлерова пути в графе. В графе "улицы" - это ребра, "перекрестки" - вершины. 1. Посчитаем степень каждой вершины (количество ребер, выходящих из нее): - Верхняя левая: 3 - Верхняя средняя: 4 - Верхняя правая: 3 - Средняя левая: 3 - Центральная: 6 - Средняя правая: 3 - Нижняя левая: 3 - Нижняя правая: 3 - Самая нижняя точка: 2 2. Выпишем вершины с нечетными степенями: - Верхняя левая (3) - Верхняя правая (3) - Средняя левая (3) - Средняя правая (3) - Нижняя левая (3) - Нижняя правая (3) Всего у нас 6 вершин с нечетными степенями. 3. Чтобы в графе существовал Эйлеров путь, в нем должно быть не более двух вершин с нечетной степенью. Сейчас их 6. Чтобы свести их количество к нулю (для Эйлерова цикла) или двум (для Эйлерова пути), нужно добавить "виртуальные" ребра или "закрыть" (удалить) существующие. По условию, мы хотим закрыть наименьшее число улиц (ребер), чтобы оставшиеся образовали Эйлеров путь. Нам нужно попарно соединить нечетные вершины, удаляя ребра. Каждое удаление ребра меняет четность двух вершин на противоположную. Количество нечетных вершин равно 6. Нам нужно получить 0 или 2. Чтобы из 6 сделать 2, нужно провести 2 операции "изменения четности", соединив пары вершин. Удаление ребра соединяет две вершины. Если мы удалим 2 ребра, мы можем изменить четность 4 вершин. 6 - 4 = 2 нечетные вершины останутся. Это позволит построить Эйлеров путь. Ответ: 2