Поликуб

Форма, сделанная из соединенных вместе кубиков

Поликуб — это объёмная фигура, образованная путём соединения одного или нескольких одинаковых кубов лицом к лицу. Поликубы — это трёхмерные аналоги плоских полимино . Куб Сомы , куб Бедлама , дьявольский куб , головоломка Слотоубера–Граатсма и головоломка Конвея — примеры задач на упаковку, основанных на поликубах. ^[1]

Перечисление поликубов

Как и полимино , поликубы можно перечислить двумя способами, в зависимости от того, считаются ли хиральные пары поликубов (эквивалентные по зеркальному отражению , но не по использованию только трансляций и вращений) одним поликубом или двумя. Например, 6 тетракубов являются ахиральными, а один — хиральным, что дает количество тетракубов 7 или 8 соответственно. ^[2] В отличие от полимино, поликубы обычно подсчитываются с учетом зеркальных пар, поскольку нельзя перевернуть поликуб, чтобы отразить его, как это можно сделать с полимино, учитывая три измерения. В частности, куб Сомы использует обе формы хирального тетракуба.

Поликубы классифицируются в зависимости от того, сколько у них кубических ячеек: ^[3]

н	Название n -поликуба	Количество односторонних n -поликубов (отражения считаются различными) (последовательность A000162 в OEIS )	Число свободных n -поликубов (отражения подсчитаны вместе) (последовательность A038119 в OEIS )
1	монокуб	1	1
2	дикуб	1	1
3	трикуб	2	2
4	тетракуб	8	7
5	пентакуб	29	23
6	гексакуб	166	112
7	гептакуб	1023	607
8	октакуб	6922	3811

Фиксированные поликубы (и отражения, и вращения считаются различными (последовательность A001931 в OEIS )), односторонние поликубы и свободные поликубы были перечислены до n = 22. Совсем недавно были исследованы конкретные семейства поликубов. ^[4]^[5]

Симметрии поликубов

Как и полимино, поликубы можно классифицировать по количеству симметрий, которые они имеют. Симметрии поликуба (классы сопряженности подгрупп ахиральной октаэдрической группы ) были впервые перечислены У. Ф. Ланноном в 1972 году. Большинство поликубов асимметричны, но многие имеют более сложные группы симметрии, вплоть до полной группы симметрии куба с 48 элементами. Существует 33 различных типа симметрии, которые может иметь поликуб (включая асимметрию). ^[2]

Свойства пентакубов

12 пентакубов плоские и соответствуют пентамино . 5 из оставшихся 17 имеют зеркальную симметрию, а остальные 12 образуют 6 хиральных пар.

Ограничивающие рамки пентакубов имеют размеры 5×1×1, 4×2×1, 3×3×1, 3×2×1, 3×2×2 и 2×2×2. ^[6]

Поликуб может иметь до 24 ориентаций в кубической решетке или 48, если допускается отражение. Из пентакубов 2 плоскости (5-1-1 и крест) имеют зеркальную симметрию по всем трем осям; они имеют только три ориентации. 10 имеют одну зеркальную симметрию; они имеют 12 ориентаций. Каждый из оставшихся 17 пентакубов имеет 24 ориентации.

Развертки октакуба и гиперкуба

Тессеракт (четырехмерный гиперкуб ) имеет восемь кубов в качестве своих граней , и так же, как куб может быть развернут в гексамино , тессеракт может быть развернут в октакуб. Одна из разверток, в частности, имитирует известную развертку куба в латинский крест : он состоит из четырех кубов, поставленных друг на друга, с еще четырьмя кубами, прикрепленными к открытым квадратным граням второго сверху куба стопки, чтобы сформировать трехмерную форму двойного креста . Сальвадор Дали использовал эту форму в своей картине 1954 года Распятие (Corpus Hypercubus)^[7] , и она описана в рассказе Роберта А. Хайнлайна 1940 года « И он построил кривой дом ». ^[8] В честь Дали этот октакуб был назван крестом Дали . ^[9]^[10] Он может замостить пространство . ^[9]

В более общем плане (отвечая на вопрос, заданный Мартином Гарднером в 1966 году), из всех 3811 различных свободных октакубов 261 являются развёртками тессеракта. ^[9]^[11]

Связность границ

Хотя кубы поликуба должны быть соединены квадрат к квадрату, квадраты его границы не обязаны быть соединены ребром к ребру. Например, 26-куб, образованный путем создания сетки 3×3×3 кубов с последующим удалением центрального куба, является допустимым поликубом, в котором граница внутренней пустоты не соединена с внешней границей. Также не требуется, чтобы граница поликуба образовывала многообразие . Например, один из пентакубов имеет два куба, которые встречаются ребром к ребру, так что ребро между ними является стороной четырех граничных квадратов.

Если поликуб обладает дополнительным свойством, заключающимся в том, что его дополнение (множество целочисленных кубов, не принадлежащих поликубу) соединено путями кубов, встречающихся квадрат с квадратом, то граничные квадраты поликуба обязательно также соединены путями квадратов, встречающихся ребро с ребром. ^[12] То есть в этом случае граница образует полиминоид .

Нерешенная задача по математике :

Можно ли развернуть каждый поликуб с соединенной границей в полимино? Если да, то можно ли развернуть каждый такой поликуб в полимино, которое замостит плоскость?

(еще нерешенные проблемы по математике)

Каждый $k$ -куб с $k < 7$ , а также крест Дали (с $k = 8$ ) можно развернуть в полимино, которое замостит плоскость. Открытой проблемой является то, можно ли развернуть каждый поликуб со связной границей в полимино, или это всегда можно сделать с дополнительным условием, что полимино замостит плоскость. ^[10]

Двойной график

Структуру поликуба можно визуализировать с помощью «дуального графа», который имеет вершину для каждого куба и ребро для каждых двух кубов, которые делят квадрат. ^[13] Это отличается от одноименных понятий дуального многогранника и дуального графа поверхностно-вложенного графа.

Двойственные графы также использовались для определения и изучения специальных подклассов поликубов, например, тех, чей двойственный граф является деревом. ^[14]

Смотрите также

Ссылки

^ Вайсштейн, Эрик В. «Поликуб». Из MathWorld
^ ab Lunnon, WF (1972), «Симметрия кубических и общих полимино», в Read, Ronald C. (ред.), Graph Theory and Computing , Нью-Йорк: Academic Press, стр. 101–108 , ISBN 978-1-48325-512-5
^ Polycubes, на The Poly Pages
^ «Перечень конкретных классов поликубов», Жан-Марк Шампарно и др., Университет Руана, Франция PDF
^ «Свертка Дирихле и перечисление пирамидальных поликубов», C. Carré, N. Debroux, M. Deneufchâtel, J. Dubernard, C. Hillairet, J. Luque, O. Mallet; 19 ноября 2013 г. PDF
^ Аартс, Рональд М. «Пентакуб». Из MathWorld.
↑ Кемп, Мартин (1 января 1998 г.), «Измерения Дали», Nature , 391 (27): 27, Bibcode : 1998Natur.391...27K, doi : 10.1038/34063
↑ Фаулер, Дэвид (2010), «Математика в научной фантастике: математика как научная фантастика», World Literature Today , 84 (3): 48– 52, doi : 10.1353/wlt.2010.0188, JSTOR 27871086, S2CID 115769478. Произведения Роберта Хайнлайна «И он построил кривой домишко», опубликованные в 1940 году, и «Профессор без сторон» Мартина Гарднера, опубликованные в 1946 году, являются одними из первых произведений в научной фантастике, знакомящих читателей с лентой Мёбиуса, бутылкой Клейна и гиперкубом (тессерактом)..
^ abc Диас, Джованна; О'Рурк, Джозеф (2015), Развертки гиперкуба, которые заполняют и , arXiv : 1512.02086 , Bibcode :2015arXiv151202086D $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$ .
^ ab Лангерман, Стефан ; Уинслоу, Эндрю (2016), «Развертки поликуба, удовлетворяющие критерию Конвея» (PDF) , 19-я Японская конференция по дискретной и вычислительной геометрии, графам и играм (JCDCG^3 2016).
^ Терни, Питер (1984), «Развертывание тессеракта», Журнал занимательной математики , 17 (1): 1– 16, MR 0765344.
^ Багчи, Амитабха; Бхаргава, Анкур; Чаудхари, Амитабх; Эппштейн, Дэвид ; Шайделер, Кристиан (2006), «Влияние неисправностей на расширение сети», Теория вычислительных систем , 39 (6): 903–928 , arXiv : cs/0404029 , doi :10.1007/s00224-006-1349-0, MR 2279081, S2CID 9332443 . См., в частности, Лемму 3.9, стр. 924, в которой излагается обобщение этого свойства граничной связности на поликубы более высокой размерности.
^ Барекет, Ронни; Барекет, Гилл; Роте, Гюнтер (2010), «Формулы и темпы роста многомерных поликубов», Combinatorica , 30 (3): 257–275 , CiteSeerX 10.1.1.217.7661 , doi :10.1007/s00493-010-2448-8, MR 2728490, S2CID 18571788 .
^ Алупис, Грег; Бозе, Просенджит К .; Коллетт, Себастьян; Демейн, Эрик Д .; Демейн, Мартин Л .; Дуеб, Карим; Дуймович, Вида ; Яконо, Джон ; Лангерман, Стефан ; Морин, Пэт (2011), «Общие развертки полимино и поликубов», Вычислительная геометрия, графики и приложения (PDF) , Конспекты лекций по Comput. наук., вып. 7033, Springer, Heidelberg, стр. 44–54 , doi :10.1007/978-3-642-24983-9_5, hdl :1721.1/73836, MR 2927309 .

Внешние ссылки

Деревянный гексакуб-пазл от Kadon
Симметрии поликуба
Программа-решатель поликубов (с исходным кодом Lua) для заполнения ящиков поликубами с использованием алгоритма X.
Перечисление поликубов Кевина Гонга

[1] Вайсштейн, Эрик В. «Поликуб». Из MathWorld

[symmetry-2] Lunnon, WF (1972), «Симметрия кубических и общих полимино», в Read, Ronald C. (ред.), Graph Theory and Computing , Нью-Йорк: Academic Press, стр. 101–108 , ISBN 978-1-48325-512-5

[3] Polycubes, на The Poly Pages

[4] «Перечень конкретных классов поликубов», Жан-Марк Шампарно и др., Университет Руана, Франция PDF

[5] «Свертка Дирихле и перечисление пирамидальных поликубов», C. Carré, N. Debroux, M. Deneufchâtel, J. Dubernard, C. Hillairet, J. Luque, O. Mallet; 19 ноября 2013 г. PDF

[6] Аартс, Рональд М. «Пентакуб». Из MathWorld.

[7] Кемп, Мартин (1 января 1998 г.), «Измерения Дали», Nature , 391 (27): 27, Bibcode : 1998Natur.391...27K, doi : 10.1038/34063

[8] Фаулер, Дэвид (2010), «Математика в научной фантастике: математика как научная фантастика», World Literature Today , 84 (3): 48– 52, doi : 10.1353/wlt.2010.0188, JSTOR 27871086, S2CID 115769478. Произведения Роберта Хайнлайна «И он построил кривой домишко», опубликованные в 1940 году, и «Профессор без сторон» Мартина Гарднера, опубликованные в 1946 году, являются одними из первых произведений в научной фантастике, знакомящих читателей с лентой Мёбиуса, бутылкой Клейна и гиперкубом (тессерактом)..

[hut-9] Диас, Джованна; О'Рурк, Джозеф (2015), Развертки гиперкуба, которые заполняют и , arXiv : 1512.02086 , Bibcode :2015arXiv151202086D $\mathbb {R} ^{3}$ $\mathbb {R} ^{2}$ .

[pucc-10] Лангерман, Стефан ; Уинслоу, Эндрю (2016), «Развертки поликуба, удовлетворяющие критерию Конвея» (PDF) , 19-я Японская конференция по дискретной и вычислительной геометрии, графам и играм (JCDCG^3 2016).

[11] Терни, Питер (1984), «Развертывание тессеракта», Журнал занимательной математики , 17 (1): 1– 16, MR 0765344.

[12] Багчи, Амитабха; Бхаргава, Анкур; Чаудхари, Амитабх; Эппштейн, Дэвид ; Шайделер, Кристиан (2006), «Влияние неисправностей на расширение сети», Теория вычислительных систем , 39 (6): 903–928 , arXiv : cs/0404029 , doi :10.1007/s00224-006-1349-0, MR 2279081, S2CID 9332443 . См., в частности, Лемму 3.9, стр. 924, в которой излагается обобщение этого свойства граничной связности на поликубы более высокой размерности.

[13] Барекет, Ронни; Барекет, Гилл; Роте, Гюнтер (2010), «Формулы и темпы роста многомерных поликубов», Combinatorica , 30 (3): 257–275 , CiteSeerX 10.1.1.217.7661 , doi :10.1007/s00493-010-2448-8, MR 2728490, S2CID 18571788 .

[14] Алупис, Грег; Бозе, Просенджит К .; Коллетт, Себастьян; Демейн, Эрик Д .; Демейн, Мартин Л .; Дуеб, Карим; Дуймович, Вида ; Яконо, Джон ; Лангерман, Стефан ; Морин, Пэт (2011), «Общие развертки полимино и поликубов», Вычислительная геометрия, графики и приложения (PDF) , Конспекты лекций по Comput. наук., вып. 7033, Springer, Heidelberg, стр. 44–54 , doi :10.1007/978-3-642-24983-9_5, hdl :1721.1/73836, MR 2927309 .