В небольшом городке 10 памятников архитектуры (рис. 2.14). Туристу хочется посетить их все, не проходя дважды по одной и той же улице. Может ли он это сделать?
На схеме памятники обозначены десятью флажками. Условие запрещает повторять улицы, но разрешает проходить через перекрёсток несколько раз, если каждый раз идти по новой улице.
Можно начать от верхнего правого флажка и двигаться по улицам схемы к флажкам верхнего ряда, затем к памятникам в средней части и закончить у нижнего правого флажка. При выборе следующего поворота не заходят в тупиковую ветвь, пока не осмотрен её памятник: из тупика пришлось бы возвращаться по той же улице. У каждого флажка можно выбрать продолжение по ещё не пройденной улице, поэтому маршрут без повторения улиц возможен.
Да, может.
