ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ
удк 548.1, 519.148
АЛГОРИТМ И КОМПЬЮТЕРНАЯ ПРОГРАММА ПЕРЕБОРА ВАРИАНТОВ УПАКОВОК ПОЛИМИНО В ПЛОСКОСТИ
© 2013 г. А. В. Малеев
Владимирский государственный университет E-mail: andr_mal@mail.ru Поступила в редакцию 28.09.2012 г.
Разработаны алгоритм и компьютерная программа перебора всех возможных периодических упаковок заданного набора полимино с заданным коэффициентом упаковки. Алгоритм основан на использовании метода дискретного моделирования молекулярных упаковок.
DOI: 10.7868/S0023476113040140
ВВЕДЕНИЕ
Геометрические проблемы заполнения пространства фигурами и разбиения пространства на фигуры были в центре внимания кристаллографии практически с момента ее зарождения. Геометрический анализ возможных периодических разбиений позволил разработать теорию симметрии кристаллических структур [1], составляющую основу современной практической кристаллографии. На принципе плотной упаковки, предложенном в [2] для исследования структур ионных кристаллов и металлов и обобщенном в [3] на молекулярные кристаллы, основано большинство современных методов кристал-лохимического анализа.
В методе дискретного моделирования молекулярных упаковок [4, 5] в качестве модели кристаллической структуры выступает периодическая упаковка поликубов в пространстве, а в двумерном случае — периодическая упаковка полимино в плоскости. Полимино представляет собой фигуру на плоскости, составленную из конечного числа одинаковых квадратов (клеток полимино), так что, во-первых, любая клетка полимино примыкает целой стороной к другой клетке этого полимино, во-вторых, из любой клетки полимино в любую другую клетку этого полимино можно попасть за конечное число шагов, переходя по смежным сторонам клеток.
Понятие и сам термин "полимино" ("polyomi-noes") были введены в 1953 г. [6, 7] и с тех пор привлекают внимание как любителей занимательной математики, так и профессиональных исследователей всего мира. Большой вклад в популяризацию математических задач, связанных с полими-но, внес М. Гарднер, который в рубрике "Математические игры" журнала "Scientific American" опубликовал серию статей, обсуждающих эти проблемы, а затем включил соответствующие главы в книги [8—10].
В настоящей работе предлагается алгоритм перебора всех возможных периодических упаковок заданного набора полимино с заданным коэффициентом упаковки, разработанный на основе метода дискретного моделирования упаковок.
ДВУМЕРНЫЕ УПАКОВОЧНЫЕ ПРОСТРАНСТВА
Назовем упаковку полимино нормальной, если центры всех клеток всех полимино принадлежат одной квадратной решетке О, элементарная ячейка которой совпадает с клетками полимино. Упаковка фигур в плоскости называется периодической, если ее группа симметрии содержит в качестве подгруппы двумерную решетку трансляций Г. В нормальной периодической упаковке полимино решетка трансляций Г является подре-шеткой по отношению к решетке О.
Одним из основных понятий метода дискретного моделирования упаковок является упаковочное пространство. В двумерном случае упаковочным пространством (УП) называется двумерная решетка О, на узлах (х, у) которой (точках УП) задана функция g(x, у), такая что множество всех узлов, дающих одинаковое значение этой функции, задает одну из двумерных подрешеток Г решетки О. Подрешетку Г в решетке О можно за-(щ щ ^
дать матрицей У = 1 I, где их, и2, v2 — целые
^ 0 )
числа, v22 > 0, 0 < и2 < щ. Столбцы матрицы У задают один из базисов подрешетки Г в базисе решетки О. Матрицу У называют матрицей УП. Индекс N = щу 2 подрешетки Г называется порядком УП. В качестве функции g(x,у), определяющей веса точек УП, можно взять функцию g(x,у) =
= \ — г V щ + <Х—[у/у2]и21 щ, — целая часть
и / 21 I Щ / 1
п л < п 1 л с £ п л См п 1 А с
I О О О < О
* 2 3 4 5 6 6 ч 1 2 3 4 5 5 1 2 3 4 4 5 > 1 2 3
0 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0
0 2 3 4 5 6 4 5 6 0 1 2 3 1 2 3 4 5 6 0 5 6 0 1 2 3 4
0 2 3 4 5 6 3 4 5 6 0 1 2 6 0 1 2 3 4 5 2 3 4 5 6 0 1
0 2 3 4 5 6 2 3 4 5 6 0 1 4 5 6 0 1 2 3 6 0 1 2 3 4 5
0 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2
7 0
I 0 1 У
7 1 I 0 1 у
7 2 I 0 1 у
7 3 I 0 1 у
-2- -3- -4- -5- -6- 9« -2- -3- -5- -6-
3 4 5 1 2 2 3 4 5 1
6 0 1 2 3 4 5 4 5 6 0 1 2 3
2 3 4 5 6 0 1 6 0 1 2 3 4 5
5 6 0 1 2 3 4 1 2 3 4 5 6 0
1 2 3 4 5 6 0 3 4 5 6 0 1 2
4 5 6 0 1 2 3 5 6 0 1 2 3 4
/ \ / л
7 4 V 0 1 у
^ 4 и
1 2 3 4 5
2 3 4 5 6 0 1
3 4 5 6 0 1 2
4 5 6 0 1 2 3
5 6 0 1 2 3 4
6 0 1 2 3 4 5
>- -Ю 0 0 0 0 0
1 1 1 1 1 1
2 2 2 2 2 2
3 3 3 3 3 3
4 4 4 4 4 4
5 5 5 5 5 5
6 6 6 6 6 6
7 5 7 6 1 0
V 01 у V 01 у V 0 7 у
Рис. 1. Фрагменты всех восьми двумерных упаковочных пространств 7-го порядка.
числа (ближайшее к q целое число, не превосходящее q), а [д] = д - [д] — дробная часть числа д. Число двумерных УП порядка N определяется
суммой делителей числа N: с(Щ = ^^ ^. На
рис. 1 приведены фрагменты всех восьми возможных двумерных УП 7-го порядка.
Назовем множество точек УП с координатами 0 < х < и1 -1 и 0 < у < v2 -1 фундаментальной областью УП. Очевидно, что фундаментальная область УП содержит ровно по одной точке УП каждого веса от 0 до N -1. Для заданного веса g координаты точки фундаментальной области УП с этим весом можно рассчитать по формулам:
) = [g/ и1], 1*^) = g - У^)Щ.
НЕЗАВИСИМЫЕ УПАКОВОЧНЫЕ ПРОСТРАНСТВА
Назовем два УП связанными, если подрешет-ки, задаваемые этими УП, могут быть совмещены комбинацией поворотов и отражений, соответствующих перестановкам и переменам знаков координат узлов исходной решетки [11]. Все возможные перестановки и перемены знаков координат узлов двумерной решетки образуют группу W, состоящую из восьми элементов. Каждому из элементов этой группы соответствует преобразование, представляемое умножением слева вектора-столбца координат точки на матрицу размера 2 х 2, в каждой строке и каждом столбце которой лишь один элемент отличен от нуля и равен либо 1, либо —1:
W =
1 0^ (-1 0
0 1 А 0 1
1 0 0 -1
-1 0 0 -1
Исходя из этого, отношение связанности УП на матричном языке можно сформулировать следующим образом.
Два УП, заданные матрицами А и В, называются связанными, если хотя бы для одной из восьми матриц Р е W выполняется равенство:
0 1 1 0
0 - 1Л 1 0
0 1Л -1 0
0 - 1Л -1 0
(РА)-1В = и,
где и — целочисленная унимодулярная (| ёе! и\ = 1) матрица.
Отношение связанности УП есть отношение эквивалентности, поэтому оно разбивает множество УП заданного порядка на непересекающиеся
0 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6
0 2 3 4 5 6 6 0 1 2 3 4 5 5 6 0 1 2 3 4 4 5 6 0 1 2 3
0 2 3 4 5 6 5 6 0 1 2 3 4 3 4 5 6 0 1 2 1 2 3 4 5 6 0
0 2 3 4 5 6 4 5 6 0 1 2 3 1 2 3 4 5 6 0 5 6 0 1 2 3 4
0 2 3 4 5 6 3 4 5 6 0 1 2 6 0 1 2 3 4 5 2 3 4 5 6 0 1
0 2 3 4 5 6 2 3 4 5 6 0 1 4 5 6 0 1 2 3 6 0 1 2 3 4 5
0 2 3 4 5 6 1 2 3 4 5 6 0 2 3 4 5 6 0 1 3 4 5 6 0 1 2
V 0 0 Ч Ч' \ Ч7Д V 0 0 Ч V 0 0 ч / л 7 3 V 0 1 у
0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 0 0 0 0 0 0
3 4 5 6 0 1 2 2 3 4 5 6 0 1 1 2 3 4 5 6 0 1 1 1 1 1 1 1
6 0 1 2 3 4 5 4 5 6 0 1 2 3 2 3 4 5 6 0 1 2 2 2 2 2 2 2
2 3 4 5 6 0 1 6 0 1 2 3 4 5 3 4 5 6 0 1 2 3 3 3 3 3 3 3
5 6 0 1 2 3 4 1 2 3 4 5 6 0 4 5 6 0 1 2 3 4 4 4 4 4 4 4
1 2 3 4 5 6 0 3 4 5 6 0 1 2 5 6 0 1 2 3 4 5 5 5 5 5 5 5
4 5 6 0 1 2 3 5 6 0 1 2 3 4 6 0 1 2 3 4 5 6 6 6 6 6 6 6
7 4 V 0 1 у
Рис. 2. Проверка критерия существования трансляционной упаковки гексамино "Ч" с коэффициентом упаковки к = 6/7.
классы. В двумерном случае УП одного класса можно упорядочить следующим образом. Если
два УП заданы матрицами У =
и1 и2
0 V 2
и У =
, будем считать, что У ^ У тогда и только
г • Л
и1 и2
0 ^2У
тогда, когда выполняется одно из двух условий: 1)
V2 < V2, 2) V2 = V2 и и2 < и\. Из всех УП одного класса независимым упаковочным пространством назовем то УП, которому соответствует наименьшая матрица УП.
ГРУППЫ ТОЧЕЧНОЙ СИММЕТРИИ УПАКОВОЧНЫХ ПРОСТРАНСТВ
Точечным симметрийным преобразованием УП назовем такое преобразование из группы Р е Ж, которое задает взаимно однозначное отображение УП на себя. Следовательно, это преобразование переводит ортонормированную решетку, на которой задано УП, саму в себя; а если какую-либо точку УП с весом g 1 это преобразование переводит в точку с весом g 2, то любую другую точку с весом g1 это преобразование также переводит в точку с весом g 2. Для того чтобы УП, за-
данное матрицей А, обладало точечным симметрийным преобразованием, заданным матрицей Р, необходимо и достаточно, чтобы выполнялось равенство:
(РА)-1А = и,
где и — целочисленная унимодулярная матрица.
Множество всех точечных симметрийных преобразований конкретного УП образуют группу, являющуюся подгруппой группы Ж.
КРИТЕРИЙ СУЩЕСТВОВАНИЯ ТРАНСЛЯЦИОННОЙ УПАКОВКИ ПОЛИМИНО
Назовем трансляционной упаковкой (ТУ) по-лимино периодическую упаковку с одним поли-мино на фундаментальную область решетки трансляций. Задание полимино сводится к заданию множества целочисленных векторов-столбцов {р¿|/ = 1,2,...,г} — координат центров клеток полимино — в базисе решетки С. Тогда критерий существования ТУ полимино можно сформулировать в виде следующей теоремы.
Теорема 1. Для того чтобы существовала трансляционная упаковка заданного полимино {в 11/ = 1,2,..., г} с коэффициентом упаковки к = г/^, необходимо и достаточно, чтобы существовало хо-
(а)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
4 5 6 0 1 2 3 4 5 6 0 1 2 3
1 2 3 4 5 6 0 1 2 3 4 5 6 0
5 6 0 1 2 3 4 5 6 0 1 2 3 4
2 3 4 5 6 0 1 2 3 4 5 6 0 1
6 0 1 2 3 4 5 6 0 1 2 3 4 5
3 4 5 6 0 1 2 3 4 5 6 0 1 2
0 1 2 3 4 5 6 0 1 2 3 4 5 6
4 5 6 0 1 2 3 4 5 6 0 1 2 3
1 2 3 4 5 6 0 1 2 3 4 5 6 0
5 6 0 1 2 3 4 5 6 0 1 2 3 4
2 3 4 5 6 0 1 2 3 4 5 6 0 1
6 0 1 2 3 4 5 6 0 1 2 3 4 5
3 4 5 6 0 1 2 3 4 5 6 0 1 2
(б)
0 1 2 3 4 5 6 0 1 2 3 4 5 6
3 4 5 6 0 1 2 3 4 5 6 0 1 2
6 0 1 2 3 4 5 6 0 1 2 3 4 5
2 3 4 5 6 0 1 2 3 4 5 6 0 1
5 6 0 1 2 3 4 5 6 0 1 2 3 4
1 2 3 4 5 6 0 1 2 3 4 5 6 0
4 5 6 0 1
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.