Упр.147 Часть 1 ГДЗ Высоцкий Ященко 7-9 класс (Алгебра)

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

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

Такой план можно изобразить, например, в виде графа с шестью вершинами, расположенными по окружности, и соединёнными так, чтобы у каждой вершины было по три ребра.

Ход решения

В этом графе все шесть вершин имеют нечётную степень, так как $$3$$ — нечётное число.

Для того чтобы можно было пройти по всем рёбрам графа, не проходя ни по одному ребру дважды, в графе должно быть не более двух вершин нечётной степени. Здесь же таких вершин шесть.

Следовательно, эйлерова цепь в этом графе не существует, и устроить такую экскурсию нельзя.

Ответ

а) Возможный план можно начертить.
б) Нельзя.