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

Решение:

Задание 147.

а) Возможный план Изумрудного города.

Нам нужно нарисовать граф с 6 вершинами (площадями), где каждая вершина имеет степень 3 (соединена с тремя другими улицами). Никакие две улицы не пересекаются, что означает, что граф является плоским.

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

Такой граф можно построить, например, расположив 3 площади в виде треугольника, и еще 3 площади между ними, соединив их соответствующим образом.

Другой вариант: представить 3 площади в виде верхнего ряда и 3 площади в виде нижнего ряда, с соответствующими соединениями.

Вот один из возможных вариантов плана:

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

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

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

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

Следовательно, устроить экскурсию по всем улицам ровно один раз невозможно.

Ответ: а) Возможный план города представлен в виде SVG-изображения. б) Нет, нельзя устроить экскурсию по всем улицам, не проходя ни по одной улице дважды, так как в графе 6 вершин с нечетной степенью.