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

Разбираем задачу:

Представим себе Изумрудный город как графы. Площади — это вершины, а улицы — это рёбра, которые их соединяют.

• У нас есть 6 площадей (вершин).
• Каждая площадь соединена ровно с 3 другими (степень каждой вершины равна 3).
• Улицы (рёбра) не пересекаются.

Задание а) Начертите возможный план:

Нам нужно нарисовать такой граф, где 6 вершин, и каждая связана ровно с тремя другими. Это называется 3-регулярный граф.

Один из возможных вариантов:

1. Нарисуем 6 точек (площадей).
2. Соединим их так, чтобы от каждой точки отходило ровно 3 линии (улицы).

Пример такого графа:

Представьте 2 треугольника, вершины которых обозначены как 1, 2, 3 и 4, 5, 6. Теперь соединим:

• 1 с 2, 1 с 3, 1 с 4
• 2 с 1, 2 с 3, 2 с 5
• 3 с 1, 3 с 2, 3 с 6
• 4 с 1, 4 с 5, 4 с 6
• 5 с 2, 5 с 4, 5 с 6
• 6 с 3, 6 с 4, 6 с 5

В этом случае каждая вершина имеет степень 3.

Задание б) Экскурсия по всем улицам без повторений:

Этот вопрос относится к теме Эйлеровых графов. Задача — найти Эйлеров путь или Эйлеров цикл.

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

В нашем случае:

• У нас 6 площадей (вершин).
• Каждая площадь соединена ровно с 3 другими, то есть степень каждой вершины равна 3.
• Все 6 вершин имеют нечетную степень.

Так как у нас больше двух вершин с нечетной степенью (их ровно 6), то Эйлеров цикл или путь не существует.

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

Ответ:

а) Возможный план можно изобразить как 3-регулярный граф с 6 вершинами.

б) Нет, нельзя.