Номер 147, часть 1 — ГДЗ Вероятность и статистика 7 класс Высоцкий, Ященко

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

а) План. Сумма степеней равна $6\cdot 3=18$, поэтому в графе $18:2=9$ рёбер (улиц). Попробуем так: нарисуем большой треугольник АБВ — три площади, каждая соединена с двумя соседними по улице. Внутри него нарисуем маленький треугольник ГДЕ — ещё три площади с улицами ГД, ДЕ и ЕГ. Осталось дать каждой площади третью улицу: соединим А с Г, Б с Д и В с Е. Все шесть площадей теперь имеют по три улицы, а улицы нигде не пересекаются (внутренний треугольник «вписан» во внешний).

Замечание. Требование «улицы не пересекаются» существенно. Например, план «три площади слева, три справа, и каждая левая соединена с каждой правой» тоже даёт по три улицы у каждой площади, но начертить его без пересечений улиц нельзя, поэтому он не подходит.

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

То же самое «на пальцах»: каждый раз, когда экскурсия проходит через площадь (приходит и уходит), на ней используются две улицы. Поэтому у площади, которая не является началом или концом экскурсии, число улиц должно быть чётным. Нечётное число улиц (у нас — три) возможно только у начала и конца экскурсии, то есть не больше чем у двух площадей, а у нас таких площадей шесть.

Ответ: а) план — на рисунке; б) нет, нельзя.