В изумрудном городе шесть площадей. Каждая площадь соединены улицами ровно с тремя другими площадями, Никакие две улицы в городе не пересекаются А) начертите возможный план изумрудного города Б) можно ли устроить экскурсию по всем улицам и площадями изумрудного города, не проходя ни по одной улице дважды?

Для решения данной задачи по графам начнем с описания структуры города. ### А) Построение графа 1. **Представление города в виде графа:** - Каждая площадь будет представлена как вершина графа. - Каждая улица между площадями будет представлена как рёбра графа. 2. **Структура графа:** - У нас есть 6 площадей (вершин), и каждая из площадей соединена ровно с тремя другими площадями. Это значит, что каждая вершина графа имеет степень 3. 3. **Граф с шестью вершинами и степенью 3:** - Для графа с 6 вершинами и степенью 3 каждую вершину необходимо соединить с 3 другими. Однако, чтобы такой граф был возможен, он должен удовлетворять определенным условиям. В частности, для неориентированного графа с \( n \) вершинами сумма степеней всех вершин должна быть четной. Так как каждое ребро соединяет две вершины, и степень каждой вершины в нашем случае равна 3, сумма степеней будет равна \( 6 \times 3 = 18 \), что является четным числом. Теперь, чтобы нарисовать возможный план изумрудного города, мы можем воспользоваться следующим примером: ``` (1) / | \ (2)--(3) | \ | (4)--(5) \ | (6) ``` - В этом графе: - Площадь 1 соединена с площадями 2, 3 и 6. - Площадь 2 соединена с площадями 1, 3 и 4. - Площадь 3 соединена с площадями 1, 2 и 5. - Площадь 4 соединена с площадями 2, 5 и 6. - Площадь 5 соединена с площадями 3, 4 и 6. - Площадь 6 соединена с площадями 1, 4 и 5. ### Б) Экскурсия по всем улицам и площадям Теперь давайте ответим на вторую часть вопроса: можно ли устроить экскурсию по всем улицам и площадям города, не проходя по одной улице дважды. Для решения этой задачи нужно выяснить, существует ли в графе "эйлеров цикл" или "эйлеров маршрут": - **Эйлеров цикл:** Это цикл, который проходит по всем рёбрам графа ровно один раз и возвращается в исходную вершину. Для его существования в неориентированном графе необходимо, чтобы все вершины имели четную степень. - **Эйлеров маршрут:** Это маршрут, который также проходит по всем рёбрам графа ровно один раз, но не обязательно возвращается в исходную вершину. Для его существования в неориентированном графе необходимо, чтобы не более чем две вершины имели нечетную степень. В нашем случае: - Все вершины имеют степень 3 (нечетная степень). Это значит, что в графе есть шесть вершин с нечетной степенью. Поскольку для существования эйлерова маршрута не должно быть более двух вершин с нечетной степенью, в нашем городе невозможно провести экскурсию, не проходя ни по одной улице дважды. ### Ответ: А) Граф, представляющий план города, можно изобразить, как показано выше. Б) Нельзя устроить экскурсию по всем улицам и площадям, не проходя по одной улице дважды.