Предложенная Уильямом Гамильтоном головоломка «кругосветного путешествия» по додекаэдру состояла в том, чтобы пройти через все вершины додекаэдра (символизирующие города), побывав в каждой ровно один раз. Головоломку можно реализовать даже с детьми: из нута и зубочисток двух типов — символизирующих пройденные и непройденные рёбра.
Самим Гамильтоном была предложена и другая реализация игры: рассматривать соответствующий плоский граф. Сделать её можно, ввинтив саморезы в плоскую доску.
На одном из простейших примеров — кубе — можно убедиться, что маршрут обхода всех вершин может иметь разную длину и, конечно, интересно находить кратчайший.
Эйлеровым циклом называется замкнутый путь, проходящий по всем рёбрам графа и притом только по одному разу. Известная с детства формулировка — какие картинки-графы можно нарисовать, не отрывая карандаша и не обводя рёбра больше одного раза. Соответствующие головоломки можно изготовить тем же способом, а используя разные графы можно получать головоломки разной сложности.
Некогда «игрушечные» задачи — поиска гамитонова или эйлерова цикла в графе — теперь находят применения в современных естественнонаучных задачах, например, при реконструкции генома.
Littérature
От прогулок по Кёнигсбергу до реконструкции генома // Математическая составляющая / Ред.-сост. Н. Н. Андреев, С. П. Коновалов, Н. М. Панюнин. — Второе издание, расширенное и дополненное. — М. : Математические этюды, 2019. — Стр. 13.
Autres modèles dans en “FRFRFR”
