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

Для решения этой задачи, нужно воспользоваться теорией графов, а именно, теоремой Эйлера.

Теорема Эйлера гласит:

• Граф содержит эйлеров путь (можно пройти по каждому ребру ровно один раз), если в графе не более двух вершин с нечетной степенью (количеством ребер, выходящих из вершины).
• Граф содержит эйлеров цикл (можно начать и закончить в одной и той же вершине, пройдя по каждому ребру ровно один раз), если все вершины имеют четную степень.

Рассмотрим каждый из представленных графов и определим минимальное количество улиц, которые нужно закрыть:

1. Первый граф:

• Подсчитаем степени вершин:
• Верхняя левая вершина: степень 3
• Верхняя правая вершина: степень 3
• Центральная вершина: степень 6
• Нижняя левая вершина: степень 3
• Нижняя правая вершина: степень 3

В графе 4 вершины с нечетной степенью. Чтобы граф имел эйлеров путь, нужно, чтобы нечетных вершин было не больше двух. Следовательно, нужно «убрать» 2 нечетные вершины, закрыв улицы, инцидентные этим вершинам.

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

2. Второй граф:

• Подсчитаем степени вершин:
• Верхняя вершина: степень 4
• Левая вершина: степень 3
• Центральная вершина: степень 5
• Нижняя вершина: степень 3
• Правая вершина: степень 3

В графе 4 вершины с нечетной степенью. Чтобы граф имел эйлеров путь, нужно, чтобы нечетных вершин было не больше двух. Следовательно, нужно «убрать» 2 нечетные вершины, закрыв улицы, инцидентные этим вершинам.

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

3. Третий граф:

• Подсчитаем степени вершин:
• Верхняя левая вершина: степень 3
• Верхняя правая вершина: степень 3
• Центральная вершина: степень 4
• Нижняя левая вершина: степень 3
• Нижняя правая вершина: степень 3

В графе 4 вершины с нечетной степенью. Чтобы граф имел эйлеров путь, нужно, чтобы нечетных вершин было не больше двух. Следовательно, нужно «убрать» 2 нечетные вершины, закрыв улицы, инцидентные этим вершинам.

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

Ответ: 2