Hiperkostka n

Hiperkostka n (zwana także n‑wymiarową kostką lub n‑kostką) jest ogólną odmianą zwykłej sześciennej kostki, rozciągniętą na wymiar naturalny n. Formalnie jest to graf będący produktem kartezjańskim K₂ × K₂ × … × K₂ (n‑krotnym), gdzie K₂ oznacza dwuwierzchołkowy graf (krawędź). Dla n = 1 hiperkostka jest po prostu odcinkiem, dla n = 2 – kwadratem, a dla n = 3 – sześcianem.

Definicja formalna

Niech V będzie zbiorem wierzchołków

V = { (x₁, x₂, …, xₙ) | xᵢ ∈ {0,1} }

i niech dwa wierzchołki u = (u₁,…,uₙ) oraz v = (v₁,…,vₙ) będą połączone krawędzią wtedy i tylko wtedy, gdy ich współrzędne różnią się w dokładnie jednej pozycji:

u ~ v ⇔ |{ i | uᵢ ≠ vᵢ }| = 1.

Zbiór V wraz z tak określoną relacją sąsiedztwa tworzy hiperkostkę n.

Podstawowe własności

• Liczba wierzchołków: 2ⁿ.
• Liczba krawędzi: n·2ⁿ⁻¹ – każda z n współrzędnych może być „przełączona” w połowie wierzchołków.
• Stopień każdego wierzchołka: n (graf regularny n‑regularny).
• Średnica (największa odległość w grafie): n – dwóch przeciwległych wierzchołków różni się we wszystkich współrzędnych.
• Wymiar topologiczny: n.
• Hiperkostka jest grafem dwudzielnym; podział na zbiór wierzchołków o parzystej i nieparzystej liczbie jedynek.

Powierzchnia i objętość (geometria euklidesowa)

Jeżeli hiperkostkę n osadzimy w przestrzeni euklidesowej ℝⁿ z krawędzią długości a, to:

• Powierzchnia (suma pól wszystkich (n‑1)-wymiarowych „ścian”) wynosi 2·n·aⁿ⁻¹.
• Objętość (n‑wymiarowa) wynosi aⁿ.

Hiperkostka a teoria grafów

Hiperkostka n jest szczególnym przypadkiem hipergrupy Cayleya oraz jedną z najprostszych struktur używanych w teorii grafów do testowania algorytmów:

• Trasy Hamiltona – w hiperkostce istnieje Hamiltonowski cykl dla każdego n ≥ 2.
• Rozmieszczenie kolorów – chromatyczność wynosi 2 (graf dwudzielny).
• Problem najkrótszej ścieżki – odległość Hammingowa pomiędzy dwoma wierzchołkami jest równoważna liczbie różniących się współrzędnych.

Zastosowania

Hiperkostka n znajduje zastosowanie w wielu dziedzinach:

• Algorytmy równoległe – struktura połączeń w rozproszonych systemach pamięci (np. sieci mesh).
• Kodowanie i korekcja błędów – przestrzenie kodów Hammingowych opierają się na odległości Hammingowej, czyli właśnie metrze hiperkostki.
• Sztuczna inteligencja i uczenie maszynowe – przeszukiwanie dużych przestrzeni binarnych (np. problem SAT).
• Geometria dyskretna – badanie wielościanów i ich projekcji (np. polytopów).
• Fizyka teoretyczna – modele wielowymiarowych przestrzeni w teorii strun.

Historia

Pierwsze wzmianki o hiperkostce pojawiły się w pracach Leibniza z XVII wieku, jednak formalne ujęcie w matematyce nastąpiło dopiero w XIX wieku w dziełach Georga Cantora i Ludwiga Schläfli. Termin hiperkostka został spopularyzowany w połowie XX wiecznego w książkach J. von Neumanna oraz w pracach Claude’a Shannona nad kodowaniem binarnym.

Warianty i pokrewne pojęcia

• Hiperkostka 2 – czyli zwykły kwadrat.
• Hiperkostka 3 – czyli sześcian.
• Hiperkostka 4 (tesseract) – czterowymiarowa kostka.
• Hipergraf – uogólnienie grafu, w którym krawędzie mogą łączyć więcej niż dwa wierzchołki.
• Środowisko binarne – przestrzeń wszystkich ciągów zer i jedynek, której podzbiorem jest hiperkostka n.

Przykłady

n	Liczba wierzchołków	Liczba krawędzi	Stopień wierzchołka
1	2	1	1
2	4	4	2
3	8	12	3
4	16	32	4
5	32	80	5

Bibliografia

• J. von Neumann, Mathematical Foundations of Quantum Mechanics, 1955.
• C. E. Shannon, The Theory of Information, 1948.
• G. Cayley, On the Theory of Groups as depending on the number of elements in the group, 1854.
• L. Schläfli, Räumliche Stöchiometrie, 1852.

Artykuł pochodzi z Encyklopedii, sekcja poświęcona geometrii i teorii grafów.