№ План города и эйлеров путь
В Изумрудном городе шесть площадей. Каждая площадь соединена улицами ровно с тремя другими площадями. Никакие две улицы в городе не пересекаются. а) Начертите возможный план Изумрудного города. б) Можно ли устроить экскурсию по всем улицам и площадям Изумрудного города, не проходя ни по одной улице дважды?
Решение
а) Изобразим три площади вершинами большого треугольника, а три площади — вершинами малого треугольника внутри него. Проведём улицы по сторонам обоих треугольников и соединим соответствующие вершины с , с , с . Эти соединяющие улицы можно расположить в трёх разных угловых областях, поэтому они не пересекаются. У каждой площади две улицы идут к соседям по своему треугольнику и одна — к площади другого треугольника. Итого степень каждой вершины .
б) Экскурсия без повторения улиц, охватывающая все улицы, была бы эйлеровым путём по этому графу. По условию степень каждой из шести площадей равна , то есть все шесть вершин нечётные. Теорема § допускает для эйлерова пути не более двух нечётных вершин. Поскольку , пройти все улицы без повторений нельзя.
Ответ
а) Два вложенных треугольника с тремя соединяющими улицами; б) нет, потому что все шесть площадей имеют нечётную степень .
