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

Ответ: а) План Изумрудного города ниже, б) Нет, нельзя

а) План Изумрудного города:

Один из возможных планов Изумрудного города, где каждая из шести площадей соединена улицами ровно с тремя другими площадями, выглядит следующим образом:

б) Ответ:

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

Ответ: а) План Изумрудного города выше, б) Нет, нельзя