Policub

Un policub este un corp geometric format prin lipirea unuia sau mai multor cuburi față la față. Policuburile sunt analoagele tridimensionale ale poliominourilor plane. Cubul Soma, Cubul Bedlam, Cubul Diabolic, Puzzle Slothouber–Graatsma și Puzzle Conway sunt exemple de probleme de împachetare care se bazează pe policuburi.^[1]

Enumerarea policuburilor

Ca și poliominourile, policuburile pot fi enumerate în două moduri, în funcție de faptul dacă perechile de policuburi chirale sunt enumerate ca un singur policub sau ca două. De exemplu 6 tetracuburi au simetrie în oglindă și unul este chiral, oferind un număr de 7, respectiv 8 tetracuburi.^[2] Spre deosebire de poliominouri, policuburile sunt de obicei enumerate ca perechi în oglindă distincte, deoarece nu se poate întoarce un policub pentru a obține imaginea sa în oglindă așa cum se poate face cu un poliomino în spațiul tridimensional. De exemplu Cubul Soma folosește ambele forme ale tetracubului chiral.

Policuburile sunt clasificate în funcție de numărul de celule cubice pe care le au:^[3]

n	Numele policubului	Numărul de policuburi (reflexiile sunt distincte^[4])	Numărul de policuburi (reflexiile sunt aceleași^[5]
1	monocub	1	1
2	dicub	1	1
3	tricub	2	2
4	tetracub	8	7
5	pentacub	29	23
6	hexacub	166	112
7	heptacub	1023	607
8	octacub	6922	3811

Policuburile au fost enumerate până la n = 16.^[6] Recent, au fost studiate familii particulare de policuburi.^[7]^[8]

Simetriile policuburilor

Ca și poliominourile, policuburile pot fi clasificate în funcție de câte simetrii au. Simetriile policuburilor (clasele de conjugare ale subgrupurilor grupului octaedric achiral) au fost enumerate pentru prima dată de WF Lunnon în 1972. Majoritatea policuburilor sunt asimetrice, dar multe au grupuri de simetrie mai complexe, până la grupul complet de simetrie al cubului, cu 48 de elemente. Sunt posibile numeroase alte simetrii; de exemplu, există șapte forme posibile de simetrie de ordinul 8.^[2]

Proprietăți ale pentacuburilor

12 pentacuburi sunt plane și corespund cu pentominourile. 5 din restul de 17 au simetrie in oglindă, iar celelalte 12 formează 6 perechi chirale.

Cutiile de delimitare ale pentacuburilor au dimensiuni 5×1×1, 4×2×1, 3×3×1, 3×2×1, 4×2×2, 3×2×2 și 2×2×2.^[9]

Un policub poate avea până la 24 de orientări într-o rețea cubică sau 48, dacă se iau în considerare reflexiile. Dintre pentacuburi, 2 plane (5-1-1 și crucea) au simetrie în oglindă în toate cele trei axe; acestea au doar trei orientări. 10 au o singură simetrie de oglindă; acestea au 12 orientări. Fiecare dintre celelalte 17 pentacuburi are 24 de orientări.

Desfășuratele octacubului și hipercubului

Tesseractul (hipercubul cvadridimensional) are opt cuburi ca fațete și, la fel cum un cub poate fi desfășurat într-un hexamino, tesseractul poate fi desfășurat într-un octacub. În special una dintre desfășurate este asemănătoare cu o cruce latină: constă din patru cuburi stivuite în coloană, cu alte patru cuburi lipite de celelalte fețe pătrate ale unui al doilea cub din coloană, pentru a forma o formă tridimensională, crucea Dalí. Salvador Dalí a folosit această formă în pictura sa Crucifixión (română Răstignire) din 1954. ^[10]^[11]^[12] Aceeași desfășurată a unui tesseract este esențială pentru intriga nuvelei —And He Built a Crooked House— (română Și el construi o casă în dungă, o casă în dungă) de Robert A. Heinlein.^[13] Această desfășurată poate tesela spațiul.^[11] Răspunzând la o întrebare pusă în 1966 de Martin Gardner, dintre cele 3811 de octacuburi diferite, 261 sunt desfășurare ale tesseractului.^[11]^[14]

Conexiuni pe frontieră

Deși cuburile unui policub trebuie să fie lipite pătrat la pătrat, pătratele de la capetele sale nu trebuie să fie conectate latură la latură. De exemplu, cubul format din 26 de cuburi prin realizarea unei rețele de 3×3×3 de cuburi și apoi scoaterea cubului central este un policub valid, în care frontiera golului interior nu este conectată la frontiera exterioară. De asemenea, nu este necesar ca frontiera unui policub să formeze o varietate. De exemplu, unul dintre pentacuburi are patru cuburi care se întâlnesc în jurul unei laturi, ca urmare acea latură face parte din patru pătrate care mărginesc cuburile.

Dacă un policub are proprietatea suplimentară că complementul său (ansamblul de cuburi care nu aparțin policubului) este conectat prin căi de cuburi care se întâlnesc pătrat la pătrat, atunci pătratele de pe frontiera policubului sunt în mod necesar conectate și prin căi de pătrate care se întâlnesc latură la latură.^[15] Adică, în acest caz frontiera formează un poliominoid.

Orice $k$ -cub cu $k<7$ inclusiv crucea Dalí (cu $k=8$ ) poate fi desfășurat ca un poliomino care poate pava planul. Este o problemă deschisă dacă fiecare policub cu o frontieră conectată poate fi desfășurat ca un poliomino sau dacă acest lucru se poate face întotdeauna cu condiția suplimentară ca acest poliomino să poată pava un plan.^[12]

Grafuri duale

Structura unui policub poate fi vizualizată prin intermediul unui „graf dual” care are câte un nod pentru fiecare cub și câte o muchie între fiecare două cuburi care au un pătrat comun.^[16] Acest lucru este diferit de noțiunile de poliedru dual și graf dual al unui graf de pe suprafață.

Grafurile duale au fost utilizate și pentru a defini și studia subclasele particulare ale policuburilor, cum ar fi cele al căror graf dual este un arbore.^[17]

Note

^ en Eric W. Weisstein, Polycube la MathWorld.
^ ^a ^b en Lunnon, W. F. (1972). „Symmetry of Cubical and General Polyominoes”. În Read, Ronald C. Graph Theory and Computing. New York: Academic Press. pp. 101–108. ISBN 978-1-48325-512-5.
^ en Polycubes, The Poly Pages, accesat 2021-06-05
^ Șirul A000162 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
^ Șirul A038119 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)
^ en Kevin Gong's enumeration of polycubes
^ en Jean-Marc Champarnaud et al, "Enumeration of Specific Classes of Polycubes" (PDF), Université de Rouen, France, accesat 2021-06-05
^ en C. Carré, N. Debroux, M. Deneufchâtel, J. Dubernard, C. Hillairet, J. Luque, O. Mallet, "Dirichlet convolution and enumeration of pyramid polycubes" (PDF), 19 noiembrie 2013, accesat 2021-06-05
^ en Eric W. Weisstein, Pentacube la MathWorld.
^ en Kemp, Martin (1 ianuarie 1998), „Dali's dimensions”, Nature, 391 (6662): 27, Bibcode:1998Natur.391...27K, doi:10.1038/34063 
^ ^a ^b ^c en Diaz, Giovanna; O'Rourke, Joseph (2015), Hypercube unfoldings that tile $\mathbb {R} ^{3}$ and $\mathbb {R} ^{2}$ , arXiv:1512.02086 , Bibcode:2015arXiv151202086D .
^ ^a ^b en Langerman, Stefan; Winslow, Andrew (2016), „Polycube unfoldings satisfying Conway's criterion” (PDF), 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2016) .
^ en Henderson, Linda Dalrymple (noiembrie 2014), „Science Fiction, Art, and the Fourth Dimension”, În Emmer, Michele, Imagine Math 3: Between Culture and Mathematics, Springer International Publishing, pp. 69–84, doi:10.1007/978-3-319-01231-5_7
^ en Turney, Peter (1984), „Unfolding the tesseract”, Journal of Recreational Mathematics, 17 (1): 1–16, MR 0765344 .
^ en Bagchi, Amitabha; Bhargava, Ankur; Chaudhary, Amitabh; Eppstein, David; Scheideler, Christian (2006), „The effect of faults on network expansion”, Theory of Computing Systems, 39 (6): 903–928, arXiv:cs/0404029 , doi:10.1007/s00224-006-1349-0, MR 2279081 . A se vedea în special lema 3.9, p. 924, care dă o generalizare a conectivității pe frontieră la policuburi din dimensiuni superioare.
^ Barequet, Ronnie; Barequet, Gill; Rote, Günter (2010), „Formulae and growth rates of high-dimensional polycubes”, Combinatorica, 30 (3): 257–275, doi:10.1007/s00493-010-2448-8, MR 2728490 .
^ en Aloupis, Greg; Bose, Prosenjit K.; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Douïeb, Karim; Dujmović, Vida; Iacono, John; Langerman, Stefan; Morin, Pat (2011), „Common unfoldings of polyominoes and polycubes”, Computational geometry, graphs and applications (PDF), Lecture Notes in Comput. Sci., 7033, Springer, Heidelberg, pp. 44–54, doi:10.1007/978-3-642-24983-9_5, MR 2927309 .

Legături externe

en An actual wooden hexacube built by Kadon
en Polycube Symmetries Arhivat în 28 ianuarie 2021, la Wayback Machine.
en Polycube solver Program (with Lua source code) to fill boxes with polycubes using Algorithm X.

Portal Matematică

[1] Eric W. Weisstein, Polycube la MathWorld.

[symmetry-2] Lunnon, W. F. (1972). „Symmetry of Cubical and General Polyominoes”. În Read, Ronald C. Graph Theory and Computing. New York: Academic Press. pp. 101–108. ISBN 978-1-48325-512-5.

[3] Polycubes, The Poly Pages, accesat 2021-06-05

[4] Șirul A000162 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[5] Șirul A038119 la Enciclopedia electronică a șirurilor de numere întregi (OEIS)

[6] Kevin Gong's enumeration of polycubes

[7] Jean-Marc Champarnaud et al, "Enumeration of Specific Classes of Polycubes" (PDF), Université de Rouen, France, accesat 2021-06-05

[8] C. Carré, N. Debroux, M. Deneufchâtel, J. Dubernard, C. Hillairet, J. Luque, O. Mallet, "Dirichlet convolution and enumeration of pyramid polycubes" (PDF), 19 noiembrie 2013, accesat 2021-06-05

[9] Eric W. Weisstein, Pentacube la MathWorld.

[10] Kemp, Martin (1 ianuarie 1998), „Dali's dimensions”, Nature, 391 (6662): 27, Bibcode:1998Natur.391...27K, doi:10.1038/34063 

[hut-11] Diaz, Giovanna; O'Rourke, Joseph (2015), Hypercube unfoldings that tile $\mathbb {R} ^{3}$ and $\mathbb {R} ^{2}$ , arXiv:1512.02086 , Bibcode:2015arXiv151202086D .

[pucc-12] Langerman, Stefan; Winslow, Andrew (2016), „Polycube unfoldings satisfying Conway's criterion” (PDF), 19th Japan Conference on Discrete and Computational Geometry, Graphs, and Games (JCDCG^3 2016) .

[13] Henderson, Linda Dalrymple (noiembrie 2014), „Science Fiction, Art, and the Fourth Dimension”, În Emmer, Michele, Imagine Math 3: Between Culture and Mathematics, Springer International Publishing, pp. 69–84, doi:10.1007/978-3-319-01231-5_7

[14] Turney, Peter (1984), „Unfolding the tesseract”, Journal of Recreational Mathematics, 17 (1): 1–16, MR 0765344 .

[15] Bagchi, Amitabha; Bhargava, Ankur; Chaudhary, Amitabh; Eppstein, David; Scheideler, Christian (2006), „The effect of faults on network expansion”, Theory of Computing Systems, 39 (6): 903–928, arXiv:cs/0404029 , doi:10.1007/s00224-006-1349-0, MR 2279081 . A se vedea în special lema 3.9, p. 924, care dă o generalizare a conectivității pe frontieră la policuburi din dimensiuni superioare.

[16] Barequet, Ronnie; Barequet, Gill; Rote, Günter (2010), „Formulae and growth rates of high-dimensional polycubes”, Combinatorica, 30 (3): 257–275, doi:10.1007/s00493-010-2448-8, MR 2728490 .

[17] Aloupis, Greg; Bose, Prosenjit K.; Collette, Sébastien; Demaine, Erik D.; Demaine, Martin L.; Douïeb, Karim; Dujmović, Vida; Iacono, John; Langerman, Stefan; Morin, Pat (2011), „Common unfoldings of polyominoes and polycubes”, Computational geometry, graphs and applications (PDF), Lecture Notes in Comput. Sci., 7033, Springer, Heidelberg, pp. 44–54, doi:10.1007/978-3-642-24983-9_5, MR 2927309 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]