Номер 147, страница 92, часть 1 - гдз по алгебре 7-9 класс учебник Высоцкий, Ященко

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

а) Начертите возможный план Изумрудного города.

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

а) Данную задачу можно смоделировать с помощью теории графов. Площади Изумрудного города будут вершинами графа, а улицы — его рёбрами. Согласно условию, нам необходимо построить граф, в котором 6 вершин, и из каждой вершины выходит ровно 3 ребра (то есть степень каждой вершины равна 3). Кроме того, граф должен быть планарным, что означает, что его можно начертить на плоскости так, чтобы рёбра (улицы) не пересекались.

Один из возможных планов города, удовлетворяющий этим условиям, представляет собой граф треугольной призмы. Его можно изобразить в виде двух треугольников, один из которых находится внутри другого. Вершины внешнего и внутреннего треугольников соединены между собой, а также каждая вершина внешнего треугольника соединена с соответствующей вершиной внутреннего.


На этом плане кружками обозначены площади (пронумерованы от 1 до 6), а линиями — улицы. Каждая площадь соединена ровно с тремя другими, и улицы не пересекаются.

Ответ: Возможный план города представлен на рисунке выше.

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

Согласно теореме, сформулированной Леонардом Эйлером, для существования эйлерова пути в связном графе необходимо и достаточно, чтобы количество вершин с нечётной степенью было равно нулю или двум.

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

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

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

Ответ: Нет, нельзя.