Парады – 2 – 7 мостов Кёнигсберга
Это карта Кёнигсберга, на которой показана протекающая через город река, остров посреди реки и семь мостов, перекинутых через реку. Жители Кёнигсберга хотели устроить парад, который бы проходил по каждому из их мостов ровно один раз. Однако им никак не удавалось найти маршрут парада, который бы охватывал все семь мостов.
CHALLENGE
Если возможно, найдите маршрут парада, который пересекает каждый из их мостов ровно один раз. Если нет, объясните, почему это невозможно.
РАЗВЕДКА
Если построить ещё один мост через реку, это упростит или усложнит решение проблемы?
Заметки
CHALLENGE
Начнем с того, что переведем эту задачу в задачу, в которой нам нужно будет пройти по ребрам. В предыдущей еженедельной головоломке «Парады» мы видели, что крайне важно, чтобы было не более двух узлов, к которым подходит нечетное число сторон.
Поскольку ко всем четырём узлам подходит нечётное число рёбер, найти маршрут парада будет невозможно!
РАЗВЕДКА
Если вы построите ещё один мост через реку в любом месте, то решить эту задачу будет очень легко.
Эта проблема возникает потому, что к двум из четырех узлов будет подходить четное число ребер.
В результате останутся только две вершины, к которым будет входить нечетное число ребер.