Физики создали самый сложный лабиринт в мире. Дедал отдыхает
Группа под руководством физика Феликса Фликера из Бристольского университета, Великобритания разработала алгоритм построения циклов на графе. Полученные циклы можно использовать, например, для абсорбции углерода и размещения его атомов на квазикристалле.
Работа опубликована в журнале Physical Review X.
Квазипериодические мозаики
Физики взяли мозаику Аммана-Бинкера. Она замечательна тем, что позволяет замостить плоскость непериодически. Что это такое. Если мы возьмем, например, квадрат, то мы легко им замостим любую площадь. Это замощение обладает свойством, которое называется трансляционной симметрией: возьмем любое подмножество замощения квадратами и сдвинем его. Подмножество обязательно совпадет с другим в другом месте. Подобных замощений очень много.
Роджер Пенроуз задался вопросом: а можно ли замостить плоскость фигурой, которая не обладает трансляционной симметрией? И он такой пример построил — это мозаика Пенроуза: если мы возьмем подмножество этой мозаики и сдвинем — мы никогда не найдем такого ее нового положения, которое совпадет с другим подмножеством этой мозаики. Будет близко, но точного совпадения не будет. Такие замощения называются квазипериодическими. Мозаика Аммана-Бинкера именно такая.
Физики попытались найти на этой мозаике так называемый цикл Гамильтона, то есть такой путь, идя по которому можно посетить каждую вершину мозаики один раз, вернуться обратно и путь нигде не пересечет себя. (Естественно такой обход строится не для бесконечной мозаики, а для ее локального подмножества). Отыскать такие пути крайне сложно. Но у ученых появилась плодотворная дебютная идея. Есть такая шахматная задача — обход всей шахматной доски конем. Действительно, если поставить коня в любую точку доски, то можно обойти ходами коня всю доску, посетив каждую клетку один раз и вернувшись обратно. Такой путь коня образует цикл Гамильтона.
Физики попытались, используя ту же идею, обойти мозаику ходом коня. И они нашли цикл Гамильтона. Вот цикл они и назвали самым сложным в мире лабиринтом. Он действительно непростой.
Квазикристаллы
Квазикристаллы — это форма материи, которая встречается в природе очень редко. Это своего рода промежуточное состояние материи — между упорядоченным и неупорядоченным.
В классическом кристалле – соли, алмазе или кварце – структура повторяется во всех трех измерениях. У этих кристаллов есть трансляционная симметрия. Вы можете взять часть этой решетки, сдвинуть и наложить ее на другую, и они идеально совпадут. В аморфном твердом теле атомы расположены хаотично. Таким телом является, например, стекло.
Квазикристалл — это материал, в котором атомы образуют узор, но трансляционной симметрии в нем нет, как в мозаике Аммана-Бинкера. Но в квазикристаллах есть так называемая «далекая симметрия»: если мы посмотрим на квазикристалл издалека, то он покажется вполне регулярным.
Используя набор двумерных мозаик Аммана-Бинкера физики получили гамильтоновы циклы, которые, по их словам, описывают атомную структуру квазикристалла. Эти циклы посещают каждый атом квазикристалла только один раз, соединяя все атомы в единую линию, которая никогда не пересекает сама себя.
Найти гамильтоновы циклы чрезвычайно сложно. Алгоритм, который помогает их отыскивать, потенциально может решить многие другие сложные математические задачи от систем поиска оптимальных маршрутов до сворачивания белков.
Квазикристаллы хорошо подходят для адсорбции углерода и для хранения водорода, для водородных двигателей. Молекулы удобно располагать как раз вдоль гамильтоновых циклов, найденных учеными.
Но все-таки самое важное значение этой работы не прикладное. Объединение столь разных идей как непериодические замощения, гамильтоновы циклы, квазикристаллы и шахматы показывает, как разные области науки проникают друг в друга и позволяют строить новые неожиданные теории.